题目描述：
有三个物种 A，B，C，其中A可以吃B，B可以吃C，C可以吃A。 给出N(N<50000)个生物，给出X(X<100000)个定论，请问X个定论中有多少是谎话？
吐槽：
刚做完GCJ想到"今天"还没有写题解，于是就坚持捉完了这个水题。可惜还是过了0点.... 残念啊
算法分析：
除了正常的并查集需要记录每个节点的父亲以外，我们还要维护该点与父亲的关系(吃? 被吃? 等价？)
判断的时候，如果i和j属于同一集合，这就不用说了....
如果parent[i]!=parent[j]，那么就将i和j所在集合合并，我的做法是将i的代表的父亲直接变为j。
维护i与新的父亲j的关系只需要改变一下parent[i]与j的关系值就好了(i本身的关系值不必改变，因为i和parent[i]的关系在那里)。
至于parent[i]和j的关系如何通过i和j的关系来确定.... 额 自己在纸上画一画就有了...
路径压缩也要维护的(很重要)... 应该很简单吧.....
1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define re1(i,n) for(int i=1;i<=n;i++)
5 int P[50001][2];
6 int find(
int x){
7 int u = P[x][0];
8 if(u==x)
return x;
9 P[x][0]=find(u);
10 P[x][1]=(P[u][1] + P[x][1])%3;
11 return P[x][0];
12 }
13 int main(){
14 int n,k;
15 scanf("%d%d",&n,&k);
16 int c,a,b,ans=0;
17 re1(i,n) P[i][0] = i, P[i][1] = 0;
18 re1(i,k){
19 scanf("%d%d%d",&c,&a,&b);
20 if(a > n || b>n) { ans ++;
continue;}
21 if(c == 1) {
22 if(find(a)!=find(b)){
23 int u = P[a][0];
24 P[u][0] = b;
25 P[u][1] = (3-P[a][1])%3;
26 }
27 else if(P[a][1]!=P[b][1]){
28 ans ++;
29 }
30 }
31 else {
32 if(a == b) ans ++;
33 else if(find(a)!=find(b)){
34 int u = P[a][0];
35 P[u][0] = b;
36 P[u][1] = P[a][1]==2?2:P[a][1]^1;
37 }
38 else if((P[a][1]-P[b][1]+3) % 3 != 1) ans++;
39 }
40 // re1(i,n) cout<<P[i][0]<<" "<<P[i][1]<<" ";cout<<endl;
41 }
42 cout<<ans<<endl;
43 44 }
45 posted on 2012-05-06 02:28
西月弦 阅读(379)
评论(7) 编辑 收藏 引用 所属分类:
解题报告 、
经典题目