(UVA) 11838 - Come and Go

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2938

也是SCC的應用喔，這題也可以當模板題。

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_N = 2004;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
int stamp[MAX_N];
bool visit[MAX_N];

void dfs_for_stamp(int id,int &cur_depth) {
    visit[id]=true;
    for (auto i=rev_edg[id].begin();i!=rev_edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_stamp(tmp,cur_depth);
    }
    stamp[cur_depth++]=id;
}

void dfs_for_scc(int id,int scc) {
    visit[id]=true;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_scc(tmp,scc);
    }
}

int main () {
    int n,m;
    while (scanf("%d %d",&n,&m) != EOF) {
        if (!n && !m) break;
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            visit[x]=false;
        }
        for (int x=0;m>x;x++) {
            int i,j,k;
            scanf("%d %d %d",&i,&j,&k);
            if (k==1) {
                edg[i].push_back(j);
                rev_edg[j].push_back(i);
            }
            else {
                edg[i].push_back(j);
                edg[j].push_back(i);
                rev_edg[i].push_back(j);
                rev_edg[j].push_back(i);
            }
        }
        int cur_depth=1;
        for (int x=1;n>=x;x++) {
            if (visit[x]==false) dfs_for_stamp(x,cur_depth);
        }
        for (int x=1;n>=x;x++) {
            visit[x]=false;
        }
        int scc=0;
        for (int x=n;x>=1;x--) {
            if (visit[stamp[x]]==false) dfs_for_scc(stamp[x],scc++);
        }
        if(scc==1) puts("1");
        else puts("0");
    }
}