UVa/11503 Virtual Friend.cpp at master · justincsd/UVa · 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
// Solved
#include<bits/stdc++.h>

using namespace std;

#define filein()       freopen("in.txt", "r", stdin)
#define fileout()      freopen("out.txt", "w", stdout)

#define MM 100008

int  p[MM], r[MM], setSize[MM];
map<string, int> m;

int findSet(int x)
{
    if (p[x]==x){
        return x;
    }
    p[x]=findSet(p[x]);
    return p[x];

}
bool isSame(int x, int y)
{
    return findSet(x)==findSet(y);
}
void unionSet(int x, int y)
{
    if (!isSame(x, y)){

        int a, b;
        a=findSet(x);
        b=findSet(y);

        if (r[a]>r[b]){
            p[b]=a;
            setSize[a]+=setSize[b];
        }
        else{
            p[a]=b;
            setSize[b]+=setSize[a];
            if(r[a]==r[b]) r[a]++;
        }
    }
}

int sizeOfSet(int i)
{
    return setSize[findSet(i)];
}
int main()
{

    int test;
    cin >> test;
    for(int i=0; i<test; i++){
        m.clear();
        int n;
        cin >> n;
        int cnt=0;
        for(int j=0; j<n; j++){
            string a, b;
            cin >> a >> b;
            if(!m.count(a)){
                setSize[cnt]=1;
                r[cnt]=0;
                p[cnt]=cnt;
                m[a]=cnt++;

            }
            if(!m.count(b)){
                setSize[cnt]=1;
                r[cnt]=0;
                p[cnt]=cnt;
                m[b]=cnt++;
            }
            unionSet(m[a], m[b]);

            cout << sizeOfSet(m[a]) << endl;
        }
    }


    return 0;
}