題目描述：
有三個(gè)物種 A，B，C，其中A可以吃B，B可以吃C，C可以吃A。 給出N(N<50000)個(gè)生物，給出X(X<100000)個(gè)定論，請(qǐng)問(wèn)X個(gè)定論中有多少是謊話(huà)？
吐槽：
剛做完GCJ想到"今天"還沒(méi)有寫(xiě)題解，于是就堅(jiān)持捉完了這個(gè)水題。可惜還是過(guò)了0點(diǎn).... 殘念啊
算法分析：
除了正常的并查集需要記錄每個(gè)節(jié)點(diǎn)的父親以外，我們還要維護(hù)該點(diǎn)與父親的關(guān)系(吃? 被吃? 等價(jià)？)
判斷的時(shí)候，如果i和j屬于同一集合，這就不用說(shuō)了....
如果parent[i]!=parent[j]，那么就將i和j所在集合合并，我的做法是將i的代表的父親直接變?yōu)閖。
維護(hù)i與新的父親j的關(guān)系只需要改變一下parent[i]與j的關(guān)系值就好了(i本身的關(guān)系值不必改變，因?yàn)閕和parent[i]的關(guān)系在那里)。
至于parent[i]和j的關(guān)系如何通過(guò)i和j的關(guān)系來(lái)確定.... 額 自己在紙上畫(huà)一畫(huà)就有了...
路徑壓縮也要維護(hù)的(很重要)... 應(yīng)該很簡(jiǎn)單吧.....
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
西月弦 閱讀(417)
評(píng)論(7) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告 、
經(jīng)典題目