union-find sets hdu 1856 more is better
More is better
1
| Mr Wang wants some boys to help him with a project. ...
|
Sample Input
1 2 3 4 5 6 7 8 9 10
| 4 1 2 3 4 5 6 1 6 4 1 2 3 4 5 6 7 8
|
Sample Output
Code
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
| #include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <vector> #include <stack> #include <deque> #include <queue> #include <bitset> #include <list> #include <map> #include <set> #include <iterator> #include <algorithm> #include <functional> #include <utility> #include <sstream> #include <climits> #include <cassert> #define BUG puts("here!!!"); using namespace std; const int N = 100005; struct Node { int par; int sum; }; int SUM; Node p[2*N + 5]; void makeSet(int n) { for(int i = 0; i <= 2*n; i++) { p[i].par = i; p[i].sum = 1; } SUM = 1; } int find(int a) { if(a == p[a].par) return a; return p[a].par = find(p[a].par); } void union1(int a, int b) { int fa = find(a); int fb = find(b); if(fa != fb) { p[fa].par = fb; p[fb].sum += p[fa].sum; } if(p[fb].sum > SUM) { SUM = p[fb].sum; } } int main() { int n, a, b; while(scanf("%d", &n) == 1) { makeSet(n); while(n--) { scanf("%d%d", &a, &b); union1(a, b); } printf("%d\n", SUM); } return 0; }
|
Checking if Disqus is accessible...