Solution UVA: 11838 - Come and Go

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11838 - Come and Go	Accepted	C++11	0.030	0.000	1110	1 mins ago

Suggest:

- If the number of strongly connected components is 1, print 1 otherwise print 0.

- I study strongly connected components at link (vietnamese). You can try or look up from internet (only need know to use template is easy to solve problem)

#include <bits/stdc++.h>

using namespace std;

const int maxN = 100010;

int n, m;

int timeDfs = 0, scc = 0;

int low[maxN], num[maxN];

bool deleted[maxN];

vector <int> g[maxN];

stack <int> st;

void dfs(int u) {

    num[u] = low[u] = ++timeDfs;

    st.push(u);

    for (int v : g[u]) {

        if (deleted[v]) continue;

        if (!num[v]){

            dfs(v);

            low[u] = min(low[u], low[v]);

        }

        else low[u] = min(low[u], num[v]);

    }

    if (low[u] == num[u]) {

        scc++;

        int v;

        do {

            v = st.top();

            st.pop();

            deleted[v] = true;

        }

        while (v != u);

    }

}

int main() {

    ios::sync_with_stdio(false); cin.tie(nullptr);

    while(cin >> n >> m){   if (n==0 && m==0) break;

       

        timeDfs=0, scc= 0;

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

            low[i]= 0, deleted[i]= false, num[i]= 0, g[i].clear();

       

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

            int u, v, z;

            cin >> u >> v >> z;

            g[u].push_back(v);

            if (z==2) g[v].push_back(u);

        }

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

            if (!num[i]) dfs(i);

   

        cout << (scc==1?1:0) <<"\n";

    }

}