題目傳送門：http://codevs.cn/PRoblem/1074/
現在才發現我這么蒟蒻，并查集都不怎么會用啊！！！
這道題似乎用了一個很巧妙（估計是我太弱）的東西，就是用 i , i+n , i+n*2 來表示 i 在 A B C 三個種類，似乎是可以輪換的
然后每讀入一次先驗證是否是假話，不是的話就合并（好像是廢話）
具體見代碼吧
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;#define LL long longint fa[150005],n,m,x,y,z,ans;int find(int x){ if (fa[x]==x) return x; fa[x]=find(fa[x]); return fa[x];}void unite(int x,int y){ x=find(x); y=find(y); if (x==y) return; fa[x]=y;}int main(){ cin>>n>>m; for (int i=1;i<=n*3;i++) fa[i]=i; for (int i=1;i<=m;i++){ cin>>z>>x>>y; if (x<0 || x>n || y<0 ||y>n){ ans++; continue; } if (z==1){ if (find(x)==find(y+n) || find(x)==find(y+n*2)){//x與y一樣時顯然不能互相吃來吃去 ans++; continue; } else{ unite(x,y); unite(x+n,y+n); unite(x+n*2,y+n*2); } } if (z==2){ if (find(x)==find(y) || find(x)==find(y+n*2)){//x吃y時x顯然不與y一樣，也不能是y吃x ans++; continue; } else{ unite(x,y+n); unite(x+n,y+n*2); unite(x+n*2,y); } } } cout<<ans;}新聞熱點
疑難解答
