PKU 1182 食物链(食物連鎖)
この問題、多分今まで5,6回は説いている気がします(笑)
なぜかというと、Union-Findの実装忘れたな〜と思うたびに解いてるからです。
今回はさすがに1発AC。Union-Findはとても大事なデータ構造なので素早く実装できないとダメなんじゃないかなと自分の中で勝手に思っています。
解法
Union-Findでゴニョゴニョ。
蟻本参照。
ソースコード>
#include <cstdio> using namespace std; int n,k; class Unionfind { public: int par[500001]; int rank[500001]; void init(int n) { for(int i=0;i<n;i++) { par[i]=i; rank[i]=0; } return; } int find(int s) { if(par[s]==s) { return s; } else { return find(par[s]); } } void unite(int a,int b) { int x=find(a); int y=find(b); if(rank[x]<rank[y]) { par[x]=y; } else { par[y]=x; if(rank[x]==rank[y])rank[x]++; } return; } bool same(int a,int b) { return find(a)==find(b); } }; int main() { scanf("%d %d",&n,&k); Unionfind uf; uf.init(n*3); int ans=0; for(int i=0;i<k;i++) { int type,x,y; scanf("%d %d %d",&type,&x,&y); x--;y--; if(x<0||x>=n||y<0||y>=n) { ans++; continue; } if(type==1) { if(uf.same(x,y+n)||uf.same(x,y+2*n)) { ans++; continue; } uf.unite(x,y);uf.unite(x+n,y+n);uf.unite(x+2*n,y+2*n); } if(type==2) { if(uf.same(x,y)||uf.same(x+n,y)) { ans++; continue; } uf.unite(x,y+n);uf.unite(x+n,y+2*n);uf.unite(x+2*n,y); } } printf("%d\n",ans); return 0; }