SHARE
TWEET

Untitled

a guest Apr 20th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define rank asdghasfastdd
  3.  
  4. using namespace std;
  5.  
  6. int parent[10000];
  7. int rank[10000];
  8.  
  9. int find_set (int v) {
  10.     if (v == parent[v])
  11.         return v;
  12.     return parent[v] = find_set(parent[v]);
  13. }
  14.  
  15. void union_sets (int a, int b) {
  16.     a = find_set(a);
  17.     b = find_set(b);
  18.     if (a != b) {
  19.         if (rank[a] < rank[b])
  20.             swap(a, b);
  21.         parent[b] = a;
  22.         if (rank[a] == rank[b])
  23.             ++rank[a];
  24.     }
  25. }
  26.  
  27. int main() {
  28.     ios_base::sync_with_stdio(false);
  29.     cin.tie(nullptr);
  30.     cout.tie(nullptr);
  31.     int n,m,ans = -1;
  32.     cin >> n >> m;
  33.     for (int i = 0; i < n; ++i) {
  34.         parent[i] = i;
  35.     }
  36.     for (int i = 0; i < m; ++i) {
  37.         int x,y;
  38.         bool b = true;
  39.         cin >> x >> y;
  40.         if (ans == -1) {
  41.             union_sets(x,y);
  42.             int t = find_set(parent[0]);
  43.             for (int j = 1; j < n; ++j) {
  44.                 if (find_set(parent[j]) != t) b = false;
  45.                 if (!b) break;
  46.             }
  47.             if (b) ans = i+1;
  48.         }
  49.     }
  50.     cout << ans << endl;
  51. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top