Come and Go

Your task is to write a program that reads a description of the city street system and determines whether the requirement of connectedness is satisfied or not.

Input 

The input contains several test cases. The first line of a test case contains two integers N and M, separated by a space, indicating the number of intersections ( 2N2000) and number of streets ( 2MN(N - 1)/2). The next M lines describe the city street system, with each line describing one street. A street description consists of three integers V, W and P, separated by a blank space, where V and W are distinct identifiers for intersections (1V, WN, VW ) and P can be 1 or 2; if P = 1 the street is one-way, and traffic goes from V to W; if P = 2 then the street is two-way and links V and W. A pair of intersections is connected by at most one street.

The last test case is followed by a line that contains only two zero numbers separated by a blank space.

Output 

Sample Input 

4 5
1 2 1
1 3 2
2 4 1
3 4 1
4 1 2
3 2 
1 2 2
1 3 2
3 2 
1 2 2
1 3 1
4 2
1 2 2
3 4 2
0 0

Sample Output 

1
1
0
0

做法 : 利用 SCC 判斷強連通元件是否只為一個


#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define maxN 2010
using namespace std;
vector<int> g[maxN];
int stk[maxN], stkIdx;
int visited[maxN], in_stk[maxN];
int vfind[maxN], findIdx;
int scc_cnt;
int scc(int nd) {
    visited[nd] = in_stk[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(!visited[*it]) {
            mn = min(mn, scc(*it));
        }
        if(in_stk[*it]) {
            mn = min(mn, vfind[*it]);
        }
    }
    if(mn == vfind[nd]) {
        scc_cnt++;
        do {
            in_stk[stk[stkIdx]] = 0;
        } while(stk[stkIdx--] != nd);
    }
    return mn;
}
int main() {
    int n, m, x, y, c;
    int i;
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0 && m == 0)
            break;
        for(i = 1; i <= n; i++) {
            g[i].clear();
            vfind[i] = visited[i] = in_stk[i] = 0;
        }
        while(m--) {
            scanf("%d %d %d", &x, &y, &c);
            g[x].push_back(y);
            if(c == 2)
                g[y].push_back(x);
        }
        scc_cnt = 0;
        for(i = 1; i <= n; i++) {
            if(!visited[i] && scc_cnt <= 1) {
                findIdx = 0, stkIdx = -1;
                scc(i);
            }
        }
        if(scc_cnt == 1)
            puts("1");
        else
            puts("0");
    }
    return 0;
}