• Source 
    1. /**************************************************************
    2.     Problem: 2079
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:3532 ms
    7.     Memory:16348 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. //by zrt
    14. //problem:
    15. using namespace std;
    16. typedef long long ll;
    17. const double eps(1e-10);
    18. int n,m;
    19. int H[200005],P[1000005],X[1000005],tot;
    20. int vis[200005];
    21. inline void add(int x,int y){
    22.     P[++tot]=y;X[tot]=H[x];H[x]=tot;
    23. }
    24. bool ok(1);
    25. int now;
    26. void find(int x){
    27.     vis[now]++;
    28.     for(int i=H[x];i;i=X[i]){
    29.         if(!vis[P[i]]){
    30.             vis[P[i]]=1;
    31.             find(P[i]);
    32.         }
    33.     }
    34. }
    35. int main(){
    36.     #ifdef LOCAL
    37.     freopen("in.txt","r",stdin);
    38.     freopen("out.txt","w",stdout);
    39.     #endif
    40.     scanf("%d%d",&n,&m);
    41.     int x,y;
    42.     while(m--){
    43.         scanf("%d%d",&x,&y);
    44.         add(x,y);
    45.         add(y,x);
    46.     }
    47.     for(int i=1;i<=n&&ok;i++){
    48.         if(!vis[i]){
    49.             vis[i]=1;
    50.             now=i;
    51.             find(i);
    52.             if(vis[i]==2) ok=0;
    53.         }
    54.     }
    55.     if(ok) puts("TAK");
    56.     else puts("NIE");
    57.     return 0;
    58. }