uvaProblems/11503cpWithRank.cpp at master · 19mddill/uvaProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;

vector<int> parent, rnk;
map<string,int>nodes;
map<int,int>group;

void makeSet(int v) {
    parent[v] = v;
    rnk[v] = 0;
    group[v] = 1;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

int union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap(a, b);
        parent[b] = a;
        group[a] += group[b];
        if (rnk[a] == rnk[b])
            rnk[a]++;
    }
    return group[a];
}

int main(){
	int tt;
	cin>>tt;
	int n = 100000;
	while(tt--){
		parent.resize(n);
		rnk.resize(n);
		int edge;
		cin>>edge;
		int a = 1;
		while(edge--){
			string s1,s2;
			cin>>s1;
			cin>>s2;
			if(nodes.find(s1) == nodes.end()){
				nodes[s1] = a;
				makeSet(a);
				a++;
			}
			if(nodes.find(s2) == nodes.end()){
				nodes[s2] = a;
				makeSet(a);
				a++;
			}
			if(find_set(nodes[s1]) != find_set(nodes[s2])){
				cout<<union_sets(nodes[s1],nodes[s2])<<endl;
			}else{
				cout<<group[find_set(nodes[s1])]<<endl;
			}
		}
		parent.clear();
		rnk.clear();
		nodes.clear();
		group.clear();
	}
}