Commits

rusydi  committed 0518af5

10685, union-find : find largest set size

  • Participants
  • Parent commits 8580538

Comments (0)

Files changed (1)

+#include<cstdio>
+#include<sstream>
+#include<cstdlib>
+#include<cctype>
+#include<cmath>
+#include<algorithm>
+#include<set>
+#include<queue>
+#include<stack>
+#include<list>
+#include<iostream>
+#include<string>
+#include<vector>
+#include<cstring>
+#include<map>
+#include<cassert>
+#include<climits>
+using namespace std;
+
+#define REP(i,n) for(int i=0, _e(n); i<_e; i++)
+#define FOR(i,a,b) for(int i(a), _e(b); i<=_e; i++)
+#define FORD(i,a,b) for(int i(a), _e(b); i>=_e; i--) 
+#define FORIT(i, m) for (__typeof((m).begin()) i=(m).begin(); i!=(m).end(); ++i)
+#define SET(t,v) memset((t), (v), sizeof(t))
+#define ALL(x) x.begin(), x.end()
+#define UNIQUE(c) (c).resize( unique( ALL(c) ) - (c).begin() )
+
+#define sz size()
+#define pb push_back
+#define VI vector<int>
+#define VS vector<string>
+
+typedef long long LL;
+typedef long double LD;
+typedef pair<int,int> pii;
+
+#define D(x) if(1) cout << __LINE__ <<" "<< #x " = " << (x) << endl;
+#define D2(x,y) if(1) cout << __LINE__ <<" "<< #x " = " << (x) \
+     <<", " << #y " = " << (y) << endl;
+
+vector<int> _set, set_size;
+
+void initSet(int N) {
+    _set.assign(N, 0);
+    set_size.assign(N, 1);
+    REP(i, N) _set[i] = i;
+}
+
+int findSet(int i) {
+    return (_set[i] == i ? i : _set[i] = findSet(_set[i]));
+}
+
+bool isSameSet(int i, int j) {
+    return findSet(i) == findSet(j);
+}
+
+void unionSet(int i, int j) {
+    if (!isSameSet(i, j)) set_size[findSet(j)] += set_size[findSet(i)];
+    _set[findSet(i)] = findSet(j);
+}
+
+int getMaxSetSize() {
+    int maxsize = set_size[0];
+    FOR(i, 1, _set.sz - 1) {
+        maxsize = set_size[i] > maxsize ? set_size[i] : maxsize;
+    }
+    return maxsize;
+}
+
+int main() {
+    int N, R;
+
+    while(cin >> N >> R && N+R) {
+        initSet(N);
+
+        map<string, int> M;
+        REP(i, N) {
+            string animal; cin >> animal;
+            M[animal] = i;
+        }
+
+        REP(i, R) {
+            string animal1, animal2;
+            cin >> animal1 >> animal2;
+            unionSet(M[animal1], M[animal2]);
+        }
+        cout << getMaxSetSize() << endl;
+
+    }
+    return 0;
+}