Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define rank asdghasfastdd
- using namespace std;
- int parent[10000];
- int rank[10000];
- int find_set (int v) {
- if (v == parent[v])
- return v;
- return parent[v] = find_set(parent[v]);
- }
- void union_sets (int a, int b) {
- a = find_set(a);
- b = find_set(b);
- if (a != b) {
- if (rank[a] < rank[b])
- swap(a, b);
- parent[b] = a;
- if (rank[a] == rank[b])
- ++rank[a];
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n,m,ans = -1;
- cin >> n >> m;
- for (int i = 0; i < n; ++i) {
- parent[i] = i;
- }
- for (int i = 0; i < m; ++i) {
- int x,y;
- bool b = true;
- cin >> x >> y;
- if (ans == -1) {
- union_sets(x,y);
- int t = find_set(parent[0]);
- for (int j = 1; j < n; ++j) {
- if (find_set(parent[j]) != t) b = false;
- if (!b) break;
- }
- if (b) ans = i+1;
- }
- }
- cout << ans << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement