Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <cstring>
- using namespace std;
- const int Maxn=int(50005);
- int na_ciklusu[Maxn];
- vector<int> E[Maxn];
- int bio[Maxn];
- struct stack{
- vector<int> niz;
- stack(){}
- void push(int x){niz.push_back(x);}
- int& top(){return niz.back();}
- void pop(){niz.pop_back();}
- void set(int x){
- for (vector<int>::reverse_iterator it=niz.rbegin();it!=niz.rend();++it){
- printf("sad stavljam: %d\n", *it+1);
- na_ciklusu[*it]=1;
- if (x==*it)break;
- }
- }
- }S;
- int t;
- int lo[Maxn],dtime[Maxn];
- int dfs(int x, int dad){
- lo[x]=1<<30;
- dtime[x]=++t;
- for (int i=0;i<E[x].size();++i){
- if (E[x][i]==dad)continue;
- if (dtime[E[x][i]]!=0){
- lo[x]=min(lo[x],dtime[E[x][i]]);
- }
- else lo[x]=min(lo[x],dfs(E[x][i],x));
- }
- if (lo[x]<=dtime[x]){
- na_ciklusu[x]=1;
- }
- return lo[x];
- }
- int n,r,m,s;
- int x,last;
- int getSG(int x, int dad){
- if (bio[x])return 0;
- bio[x]=1;
- int ret=0;
- for (int i=0;i<E[x].size();++i){
- if (E[x][i]==dad)continue;
- ret^=getSG(E[x][i],x);
- }
- if (na_ciklusu[x])return 1^ret;
- else return 1+ret;
- }
- int main(void){
- scanf("%d %d %d", &n, &m, &r); --r;
- for (int i=0;i<m;++i){
- last=-1;
- scanf("%d", &s);
- for (int j=0;j<s;++j){
- scanf("%d", &x); --x;
- if (last!=-1){
- E[x].push_back(last);
- E[last].push_back(x);
- }
- last=x;
- }
- }
- dfs(r,-1);
- //for (int i=0;i<n;++i){
- // printf("%d ", na_ciklusu[i]);
- //}puts("");
- memset(bio,0,sizeof bio);
- int s=getSG(r,-1);
- if (s)puts("First");
- else puts("Second");
- printf("%d\n", -1^1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement