11838 - Come and Go.cpp

#include<bits/stdc++.h>
using namespace std;

int n,e;
vector<int>v1[2005],v2[2005];//,comp[1005];
bool visited[2005];
int mark;
stack<int>s;

void toposort(int x){

    visited[x]=true;

    for(int i=0;i<v1[x].size();i++){

        int xx = v1[x][i];

        if(visited[xx]==false) toposort(xx);

    }

    s.push(x);

}

void dfs(int x){

    //comp[mark].push_back(x);

    //cout<<x<<" ";

    visited[x]=true;

    for(int i=0;i<v2[x].size();i++){

        int xx = v2[x][i];

        if(visited[xx]==false) dfs(xx);

    }

}

void FindScc(){

    stack<int>emp;

    swap(s,emp);

    memset(visited,false,sizeof(visited));

    mark=0;

    for(int i=1;i<=n;i++){

        if(visited[i]==false) toposort(i);

    }

    memset(visited,false,sizeof(visited));

    while(!s.empty()){

        int u = s.top();

        s.pop();

        if(visited[u]==false){

            mark++;
            dfs(u);

        }

    }

}

int main(){

    int a,b,c;
    while(cin>>n>>e){

        if(n==0 && e==0) break;

        while(e--){
            cin>>a>>b>>c;

            if(c==1){
                v1[a].push_back(b);
                v2[b].push_back(a);
            }
            else{
                v1[a].push_back(b);
                v1[b].push_back(a);
                v2[b].push_back(a);
                v2[a].push_back(b);
            }

        }

        FindScc();

        //cout<<mark<<"\n";

        if(mark==1) cout<<1<<"\n";
        else cout<<0<<"\n";

        for(int i=1;i<=n;i++){
            v1[i].clear();
            v2[i].clear();
        }

    }

    return 0;

}