UVa 11838 – Come and Go [solved]

Posted on February 19, 2020 by Mobarak Hosen Shakil — Leave a comment

/******************************************
          Mobarak Hosen Shakil
        ICE, Islamic University
     ID: mhiceiuk(all), 29698(LOJ)
   E-mail: mhiceiuk @ (Gmail/Yahoo/FB)
 Blog: https://iuconvergent.wordpress.com
*******************************************/

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

#define IOS             ios_base::sync_with_stdio(0);cin.tie(0)
#define LL              long long int
#define ULL             unsigned LL
#define READ(File)      freopen(File, "r", stdin)
#define WRITE(File)     freopen(File, "w", stdout)
#define FOR(i, a, b)    for(int i=a; i<b; i++)
#define REP(i, a, b)    for(int i=a; i>=b; i--)
#define PII             pair<int, int>
#define pb              push_back
#define nl              '\n'

#define dbl             printf("I'm here baby\n")

const int inf = 1<<30;
const LL INF  = 1e18;
const int MOD = 1e9+7;
const int MAXN = 300005;

/*** Custom Sorting ***/
bool Compare(const PII &x, const PII &y)
{
    if(x.first == y.first)
    {
        return x.second>y.second;
    }
    return x.first<y.first;
}

/** 3D Direction --> x, y, z **/
int dx[] = {-1,  1, 0,  0,  0,  0};
int dy[] = { 0,  0, 1, -1,  0,  0};
int dz[] = { 0,  0, 0,  0,  1, -1};
///          N,  S, E,  W,  U,  D

vector<int> edges[20002];
vector<int> redges[20002];
stack<int> st;
bool vis[20002];

void reset(int n)
{
    FOR(i, 0, n)
    {
        vis[i] = false;
        edges[i].clear();
        redges[i].clear();
    }
}

void DFS(int u)
{
    vis[u] = true;
    FOR(i, 0, edges[u].size())
    {
        int v = edges[u][i];
        if(!vis[v]) DFS(v);
    }
    st.push(u);
}

void DFS2(int u)
{
    vis[u] = true;
    FOR(i, 0, redges[u].size())
    {
        int v = redges[u][i];
        if(!vis[v]) DFS2(v);
    }
}

int main()
{

    int N, M;
    while(scanf("%d%d", &N, &M) && N!=0) {

        reset(N);

        FOR(i, 0, M)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            edges[a-1].pb(b-1);
            redges[b-1].pb(a-1);
            if(c==2) {
                edges[b-1].pb(a-1);
                redges[a-1].pb(b-1);
            }
        }

        FOR(i, 0, N)
        {
            if(!vis[i]) DFS(i);
        }

        memset(vis, false, sizeof(vis));
        int tot = 0;
        while(!st.empty())
        {
            int src = st.top(); st.pop();
            ///cout<<src<<' ';
            if(!vis[src])
            {
                DFS2(src);
                tot++;
            }
        }
     ///   cout<<nl;
        tot = tot>1?0:1;

        printf("%d\n",tot);
    }
    return 0;
}