题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1116
分析:
对于任意的联通块,只要有环,则可以将这个联通块链接方式变成环中互连,环中向环外连的方式。
所以只要对于任意联通块找环就好.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<bits/stdc++.h> using namespace std; template<class T>void read(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); } while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } x = f ? -x : x; return ; } int n,m; int Father[1000010]; int Find_Father(int x) { return Father[x]==x ? x : Father[x]=Find_Father(Father[x]); } bool Round[1000010]; int main() { //freopen("./in","r",stdin); int a,b; read(n);read(m); for(int i=1;i<=n;++i)Father[i]=i; for(int i=1;i<=m;++i) { read(a);read(b); int xx=Find_Father(a),yy=Find_Father(b); if(xx!=yy) { Father[yy]=xx; Round[xx]|=Round[yy]; } else { Round[xx]=true; } } bool flag=false; for(int i=1;i<=n;++i)if(!Round[Find_Father(i)])flag=true; if(!flag)printf("TAK\n"); else printf("NIE\n"); //fclose(stdin); return 0; } |
