BZOJ 1116 [POI2008]CLO 并查集

题意:链接方法:并查集解析:第一眼神题，看完hz题解后发现被D了。明明sb题。如果某个连通块里存在环那么一定会达到目标状态。为什么？自己YY:)所以并查集合并就行了。代码:;int n,m;int fa[N];int v[N];int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);}int main(){scanf(“%d%d”,&n,&m);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){int x,y;scanf(“%d%d”,&x,&y);int fx=find(x),fy=find(y);if(fx!=fy){fa[fx]=fy;v[fy]=(v[fy]==1||v[fx]==1);}else{v[fx]=1;}}for(int i=1;i<=n;i++){if(!v[find(i)]){puts(“NIE”);return 0;}}puts(“TAK”);}

，想起那座山，那个城，那些人……