uva 11838 - Come and Go

Come and Go

In a certain city there are N intersections connected by one-way and two-way streets. It is a modern city, and several of the streets have tunnels or overpasses. Evidently it must be possible to travel between any two intersections. More precisely given two intersections V and W it must be possible to travel from V to W and from W to V.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 andP, 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 

For each test case your program should print a single line containing an integer G, where G is equal to one if the condition of connectedness is satisfied, and G is zero otherwise.

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

---

Graph, SCC (Strong Connected Component)

#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,low[2000],q[2000],scnt,cp,cnt,rnum;
vector<int>egs[2000];
bool trav[2000];
void tarjan(int a){
    if(DBG)printf("scc %d eg %d\n",a,egs[a].size());
    int b,c,m;
    trav[a]=1,m=low[a]=cnt++;
    q[cp++]=a;
    rep(i,egs[a].size()){
        b=egs[a][i];
        if(!trav[b])tarjan(b);
        if(low[b]<m)m=low[b];
    }
    if(m<low[a]){low[a]=m;return;}
    if(DBG)printf("found scc %d m %d low[%d] %d\n",a,m,a,low[a]);
    rnum=cp;
    do{
        low[c=q[--cp]]=N;
    }while(c!=a);
    scnt++;
}
void ans(){
    scnt=cp=cnt=0;
    memset(trav,0,sizeof(trav));
    tarjan(0);
    if(scnt==1&&rnum==N)printf("1\n");
    else printf("0\n");
}
int main(){
    int a,b,c,m,n;
    while(scanf("%d%d",&N,&m)==2){
        if(N+m==0)break;
        rep(i,2000)egs[i].clear();
        rep(i,m){
            scanf("%d%d%d",&a,&b,&c);
            if(DBG)printf("a b c %d %d %d\n",a,b,c);
            a--,b--;
            if(c==2)egs[a].push_back(b),egs[b].push_back(a);
            else egs[a].push_back(b);
            if(DBG)printf("egs[%d]: %d\n",a,egs[a].size());
        }
        ans();
    }
}