union-find sets poj 1703 find them, catch them 帮派之争
1 2 3 4 5 6 7
| 1 5 5 A 1 2 D 1 2 A 1 2 D 2 4 A 1 4
|
Sample Output
1 2 3
| Not sure yet. In different gangs. In the same gang.
|
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
| #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 MID(x,y) ( ( x + y ) >> 1 ) #define L(x) ( x << 1 ) #define R(x) ( x << 1 | 1 ) #define BUG puts("here!!!"); #define STOP system("pause"); using namespace std; const int N = 100005; int f[N+N]; int n, m; int find(int x) { if(f[x] < 0) return x; return f[x] = find(f[x]); } int main() { int loop; cin >> loop; while(loop--) { scanf("%d%d", &n, &m); memset(f, 255, sizeof(f)); while(m--) { int a, b; char s[3]; scanf("%s%d%d", s, &a, &b); if(s[0] == 'A') { if(find(a) != find(b) && find(a) != find(b+n)) { printf("Not sure yet.\n"); } else if(find(a) == find(b)) { printf("In the same gang.\n"); } else printf("In different gangs.\n"); } else { if(find(a) != find(b+n)) { f[find(a)] = find(b+n); f[find(b)] = find(a+n); } } } } return 0; }
|
Checking if Disqus is accessible...