Advertisement
Guest User

Untitled

a guest
Aug 12th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. const int Maxn=int(50005);
  7. int na_ciklusu[Maxn];
  8. vector<int> E[Maxn];
  9. int bio[Maxn];
  10.  
  11. struct stack{
  12.     vector<int> niz;
  13.     stack(){}
  14.     void push(int x){niz.push_back(x);}
  15.     int& top(){return niz.back();}
  16.     void pop(){niz.pop_back();}
  17.     void set(int x){
  18.         for (vector<int>::reverse_iterator it=niz.rbegin();it!=niz.rend();++it){
  19.             printf("sad stavljam: %d\n", *it+1);
  20.             na_ciklusu[*it]=1;
  21.             if (x==*it)break;
  22.         }
  23.     }
  24. }S;
  25. int t;
  26. int lo[Maxn],dtime[Maxn];
  27. int dfs(int x, int dad){
  28.     lo[x]=1<<30;
  29.     dtime[x]=++t;
  30.     for (int i=0;i<E[x].size();++i){
  31.         if (E[x][i]==dad)continue;
  32.         if (dtime[E[x][i]]!=0){
  33.             lo[x]=min(lo[x],dtime[E[x][i]]);
  34.         }
  35.         else lo[x]=min(lo[x],dfs(E[x][i],x));
  36.     }
  37.     if (lo[x]<=dtime[x]){
  38.         na_ciklusu[x]=1;
  39.     }
  40.     return lo[x];
  41. }
  42.  
  43. int n,r,m,s;
  44. int x,last;
  45.  
  46. int getSG(int x, int dad){
  47.     if (bio[x])return 0;
  48.     bio[x]=1;
  49.     int ret=0;
  50.     for (int i=0;i<E[x].size();++i){
  51.         if (E[x][i]==dad)continue;
  52.         ret^=getSG(E[x][i],x);
  53.     }
  54.     if (na_ciklusu[x])return 1^ret;
  55.     else return 1+ret;
  56. }
  57.  
  58. int main(void){
  59.     scanf("%d %d %d", &n, &m, &r); --r;
  60.     for (int i=0;i<m;++i){
  61.         last=-1;
  62.         scanf("%d", &s);
  63.         for (int j=0;j<s;++j){
  64.             scanf("%d", &x); --x;
  65.             if (last!=-1){
  66.                 E[x].push_back(last);
  67.                 E[last].push_back(x);
  68.             }
  69.             last=x;
  70.         }
  71.     }
  72.     dfs(r,-1);
  73.     //for (int i=0;i<n;++i){
  74.     //    printf("%d ", na_ciklusu[i]);
  75.     //}puts("");
  76.     memset(bio,0,sizeof bio);
  77.     int s=getSG(r,-1);
  78.     if (s)puts("First");
  79.     else puts("Second");
  80.     printf("%d\n", -1^1);
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement