fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <vector>
  4. #include <cstdio>
  5. #include <ios>
  6. #include <map>
  7. #include <set>
  8. #include <algorithm>
  9. #include <cstring>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long ll;
  14.  
  15. #define N 100005
  16.  
  17. int par[N];
  18. int last[N];
  19.  
  20. int getRoot(int x){
  21.     if(par[x] == x) return x;
  22.     return par[x] = getRoot(par[x]);
  23. }
  24.  
  25. bool areSameComp(int a, int b){
  26.     return getRoot(a) == getRoot(b);
  27. }
  28.  
  29. void mergee(int a, int b){
  30.     par[getRoot(a)] = getRoot(b);
  31. }
  32.  
  33. int main() {
  34.     int n, m, a, b;
  35.     scanf("%d %d", &n, &m);
  36.     for(int i = 1; i <= n; i++){
  37.         par[i] = i;
  38.     }
  39.     int tot = 0;
  40.     for(int i = 0; i < m; i++){
  41.         ++tot;
  42.         scanf("%d %d", &a, &b);
  43.         if(areSameComp(a, b)) break;
  44.         if(last[a] != 0) mergee(last[a], b);
  45.         if(last[b] != 0) mergee(last[b], a);
  46.         if(areSameComp(a, b)) break;
  47.         last[a] = b;
  48.         last[b] = a;
  49.     }
  50.  
  51.     cout << tot << endl;
  52.  
  53.     return 0;
  54. }
Success #stdin #stdout 0s 4124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ud4foP
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!