ProgrammingProblems/uva11503.cpp at master · rishikesha/ProgrammingProblems · 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
 * Rishikesh
 * UVA 11503
 */
#include<vector>
#include<iostream>
#include<set>
#include<algorithm>
#include<numeric>
#include<string>
#include<sstream>
#include<map>

using namespace std;

class UnionFind {
    private:
        const int size;
        vector<int> parent;
        vector<int> rank;
        vector<int> count;

    public:
        UnionFind(int sz) : size(sz) {
            parent.resize(sz);
            rank.resize(sz);
            count.resize(sz);
            iota(parent.begin(), parent.end(), 0);
            fill(count.begin(), count.end(), 1);
        }

        void un(int i, int j) {
            int pi = find(i); int pj = find(j);
            if (pi == pj)
                return;
            if (rank[pj] < rank [pi])
                swap(pi, pj);
            parent[pi] = pj;
            if (rank[pi] == rank[pj])
                rank[pj]++;
            count[pj] += count[pi];
        }

        int find(int i) {
            if (parent[i] == i)
                return i;
            else {
                parent[i] = find(parent[i]);
                return parent[i];
            }
        }

        int getcount(int i) {
            return count[find(i)];
        }

};


int main() {
    int ncases;
    string s;
    getline(cin, s);
    istringstream iss;
    ncases = stoi(s);
    while(ncases--) {
        UnionFind ufset(100001);
        getline(cin,s);
        int nedges= stoi(s);
        vector<pair<string, string>> edges;
        map<string, int> nametonum;
        int serialno = 1;
        for (int i = 0 ; i < nedges; i++) {
            getline(cin, s); iss = istringstream(s);
            string n1, n2;
            iss >> n1 >> n2;

            if (nametonum.find(n1) == nametonum.end())
                nametonum[n1] = serialno++;
            if (nametonum.find(n2) == nametonum.end())
                nametonum[n2] = serialno++;

            ufset.un(nametonum[n1], nametonum[n2]);
            cout << ufset.getcount(nametonum[n1])<< endl;
        }
    }
}