Advertisement
Guest User

Untitled

a guest
Apr 30th, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, m, q, a, b, zl=2, pre[1000111], low[1000111], odw[1000111], p[1000111];
  5. vector<int> v[1000111];
  6. vector<pair<int, int> > r;
  7. void dfs(int u, int oj){
  8.     pre[u] = low[u] = zl++;
  9.     odw[u] = 1;
  10.     for(auto i = v[u].begin(); i!=v[u].end(); i++){
  11.         if( *i!=oj ){
  12.             if( !odw[*i] ){
  13.                 dfs(*i, u);
  14.                 low[u] = min(low[u], low[*i]);
  15.                 if( low[*i]>=pre[u] ) p[u] = 1;
  16.             }
  17.             else
  18.                 low[u] = min(low[u], pre[*i]);
  19.         }
  20.     }
  21. }
  22.  
  23. int main()
  24. {
  25.     scanf("%d%d", &n, &m);
  26.     for(int i = 0; i<m; i++){
  27.         scanf("%d%d", &a, &b);
  28.         r.push_back({a, b});
  29.         v[a].push_back(b);
  30.         v[b].push_back(a);
  31.     }
  32.     int ok = 0;
  33.     pre[1] = 1; odw[1] = 1;
  34.     for(int i = 0; i<v[1].size(); i++){
  35.         if( !odw[v[1][i]] ){
  36.             ok++;
  37.             dfs(v[1][i], 1);
  38.         }
  39.     }
  40.     if( ok>1 ) p[1] = 1;
  41.     scanf("%d", &q);
  42.     for(int i = 0; i<q; i++){
  43.         scanf("%d", &a);
  44.         if( p[a]==1 ) printf("NIE\n");
  45.         else printf("TAK\n");
  46.     }
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement