• Source 
    1. /**************************************************************
    2.     Problem: 1116
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:516 ms
    7.     Memory:6212 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. //dian >=3 liantong fenliang bixu you huan
    19. int H[100005],P[400005],X[400005],tot;
    20. int out[100005];
    21. inline void add(int x,int y){
    22.     P[++tot]=y;X[tot]=H[x];H[x]=tot;
    23. }
    24. int cnt,siz[100005],belong[100005],bian[100005];
    25. bool vis[100005];
    26. void find(int x){
    27.     vis[x]=1;siz[cnt]++;
    28.     belong[x]=cnt;
    29.     for(int i=H[x];i;i=X[i]){
    30.         if(!vis[P[i]]){
    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.     int n,m;
    41.     scanf("%d%d",&n,&m);
    42.     for(int i=0,x,y;i<m;i++){
    43.         scanf("%d%d",&x,&y);
    44.         out[x]++;out[y]++;
    45.         add(x,y);add(y,x);
    46.     }
    47.     for(int i=1;i<=n;i++){
    48.         if(!vis[i]){
    49.             cnt++;
    50.             find(i);
    51.         }
    52.     }
    53.     for(int i=1;i<=n;i++){
    54.         bian[belong[i]]+=out[i];
    55.     }
    56.     bool ok=1;
    57.     for(int i=1;i<=cnt&&ok;i++){
    58.         if(siz[i]<3) ok=0;
    59.         if(bian[i]<siz[i]*2) ok=0;
    60.     }
    61.     if(ok) puts("TAK");
    62.     else puts("NIE");
    63.     return 0;
    64. }