[UVa] 11838 - Come and Go

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11838 - Come and Go
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Strongly Connected Component
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
#define em            emplace_back
 
static const int maxn = 2000 + 5;
 
struct edge
{
    int u, v, t;
    edge(int u = 0, int v = 0, int t = 0) : u(u), v(v), t(t) {}
};
 
vector <edge> E;
vector <int> undirectedgraph[maxn],
             directedgraph[maxn],
             rdirectedgraph[maxn],
             topo,
             baki;
int par[maxn], cnt[maxn], total, gowithundirectededge;
bool vis[maxn], vis2[maxn], visscc[maxn];
 
void init()
{
    for (int i = 1; i < maxn; i++)
    {
        par[i] = i;
        vis[i] = 0;
        cnt[i] = 0;
        vis2[i] = 0;
        visscc[i] = 0;
        undirectedgraph[i].clear();
        directedgraph[i].clear();
        rdirectedgraph[i].clear();
    }
    E.clear();
    topo.clear();
    baki.clear();
    total = 0;
    gowithundirectededge = 0;
}
 
void dfs1(int u, int p)
{
    par[u] = p;
    gowithundirectededge++;
    cnt[p]++;
    vis[u] = 1;
    for (int v : undirectedgraph[u])
    {
        if (vis[v]) continue;
        dfs1(v, p);
    }
}
 
void dfs2(int u)
{
    vis2[u] = 1;
    for (int v : directedgraph[u])
    {
        if (vis2[v]) continue;
        dfs2(v);
    }
    topo.em(u);
}
 
void scc(int u)
{
    visscc[u] = 1;
    total += cnt[ par[u] ];
    for (int v : rdirectedgraph[u])
    {
        if (visscc[v]) continue;
        scc(v);
    }
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tnode, tedge;
    while (scanf("%d %d", &tnode, &tedge) == 2)
    {
        if (tnode+tedge == 0) break;
        init();
        for (int e = 1; e <= tedge; e++)
        {
            int u, v, t;
            scanf("%d %d %d", &u, &v, &t);
            E.em(u, v, t);
            if (t == 2)
            {
                undirectedgraph[u].em(v);
                undirectedgraph[v].em(u);
            }
        }
        int tcompo = 0;
        for (int i = 1; i <= tnode; i++) if (!vis[i]) tcompo++, dfs1(i, i);
        if (tcompo == 1 && gowithundirectededge == tnode)
        {
            puts("1");
            continue;
        }
        for (edge e : E)
        {
            if (e.t == 2) continue;
            int p = par[e.u];
            int q = par[e.v];
            if (e.u == p) cnt[p]++;
            if (e.v == q) cnt[q]++;
            baki.em(p);
            baki.em(q);
            directedgraph[p].em(q);
            rdirectedgraph[q].em(p);
        }
        if (baki.size() == 0)
        {
            puts("0");
            continue;
        }
        for (int it : baki) if (!vis2[it]) dfs2(it);
        tcompo = 0;
        for (auto it = topo.rbegin(); it != topo.rend(); it++) 
         if (!visscc[*it]) tcompo++, scc(*it);
        puts(tcompo > 1 ? "0" : "1");
    }
}