Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef string str;
- const int N = 2e5 + 3, INF = 1e5;
- int parent[N];
- ll sz[N];
- bool use[N];
- 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(sz[a] < sz[b])
- swap (a, b);
- parent[b] = a;
- sz[a] += sz[b];
- }
- }
- int main()
- {
- ios :: sync_with_stdio(0);
- cin.tie(NULL), cout.tie(NULL);
- //freopen("sum.in", "r", stdin), freopen("sum.out", "w", stdout);
- int n, q;
- map <pair <int, int>, bool> mp;
- cin >> n >> q;
- for(int i = 0; i < n; ++i) parent[i] = i, sz[i] = 1;
- while(q--){
- char c;
- int a, b;
- cin >> c >> a >> b;
- if(c == '+') union_sets(a, b), use[a] = 1, use[b] = 1;
- else if(c == '-'){
- int pa = find_set(a), pb = find_set(b);
- sz[pa] += INF, sz[pb] += INF
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement