UVA/11503.cpp at master · johan-smc/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
#include <iostream>
#include <cstdio>
#include <map>

#define foi( i , n , k ) for( int i = n ; i < k ; ++i )
using namespace std;

class UnionFind
{
  private:
    map< string , string > p;
    map< string , int > rank;
    map< string , int > nn;
  public:
    string findSet( string i )
    {
      return ((p[i]==i) ? i :(p[i]= findSet(p[i]) ));
    }
    void insert( string i )
    {
      p.insert(make_pair(i,i));
      rank.insert(make_pair(i,0));
      nn.insert(make_pair(i,1));
    }

    bool isSame( string i , string j )
    {
      return findSet(i)==findSet(j);
    }


    int max( string i )
    {
      return nn[findSet(i)];
    }

    void unionSet ( string i, string j )
    {
      if( p.find(i) == p.end() )
        insert(i);
      if( p.find(j) == p.end() )
        insert(j);
      if(!isSame(i,j))
      {
        string x,y;
        x=findSet(i);
        y=findSet(j);
        int tot=nn[x]+nn[y];
        if( rank[x] > rank[y] )
        {
          p[y]=x;
        }
        else
        {
          p[x]=y;
          if( rank[x]==rank[y] )
            rank[y]++;
        }
        nn[findSet(x)]=tot;
      }
    }
};

int main()
{
  int t;
  scanf("%d",&t );
  while( t-- )
  {
    int c;
    UnionFind uf;
    string a,b;
    scanf("%d",&c );
    foi( i , 0 , c )
    {
      cin>>a>>b;
      uf.unionSet(a,b);
      uf.unionSet(b,a);
      printf("%d\n",uf.max(a));
    }
  }
  return 0;
}