poj 1703 Find them, Catch them (并查集)
http://poj.org/problem?id=1703
种类冰茶几...看到还有一种算是拓展的交加权冰茶几？ 看到有做法是在开一个数组。。。记录是哪一组.... 但是因为只有两组....我们可以分别存... 因为不知道每一个D的两个人分别是哪个组（帮派？） 可以都存一下。 TLE了两次....应该是用了cin的事。。。改成scanf就变WA了。。。 想了下。原来是我对“not sure yet”的判断出现失误。 我开了一个v数组，记录在D下出现的人。 我误以为出现的人的帮派一定是确定的。 实际上并不是。 比如 1,3 5,7 3和7都出现了。但是3和7是一组与否显然还是“not sure yet”
1
2
3
4 /* ***********************************************
5 Author :111qqz
6 Created Time :2016年03月03日 星期四 13时43分16秒
7 File Name :code/poj/1703.cpp
8 ************************************************ */
9
10 #include <iostream>
11 #include <algorithm>
12 #include <cstring>
13 #include <cstdio>
14 #include <cmath>
15
16 using namespace std;
17
18 const int N=2E5+7;
19 bool v[N];
20 int f[N];
21 int T,n,m,x,y;
22 char ch;
23
24 int root (int x)
25 {
26 if (f[x]!=x)
27 f[x] = root(f[x]);
28 return f[x];
29 }
30 void u(int a,int b)
31 {
32 f[root(a)]=root(b);
33 }
34 void ask(int a,int b)
35 {
36 //if (!v[a]||!v[b])
37 // {
38
39 // return;
40 // }
41 if (root(a)==root(b)||root(a+n)==root(b+n))
42 {
43 cout<<"In the same gang."<<endl;
44 }
45 else if (root(a)==root(b+n)||root(a+n)==root(b))
46 {
47 cout<<"In different gangs."<<endl;
48 }
49 else
50 {
51 cout<<"Not sure yet."<<endl;
52 }
53 }
54
55
56 int main()
57 {
58 cin>>T;
59 while (T--)
60 {
61 memset(v,false,sizeof(v));
62 for ( int i = 0 ; i < N ; i++ )
63 f[i] = i;
64 scanf("%d %d",&n,&m);
65 for ( int i = 1 ; i <= m ; i++ )
66 {
67
68 scanf("%s %d %d",&ch,&x,&y);
69 if (ch=='A')
70 {
71 ask(x,y);
72 }
73 else
74 {
75 v[x] = true;
76 v[y] = true;
77 u(x,y+n);
78 u(x+n,y);
79 }
80 }
81 }
82 return 0;
83 }
84
85
86