UVa : 11838 - Come and Go

問題概要

http://uva.onlinejudge.org/external/118/11838.html
有向グラフが与えられます。
どの２つのノード間でも行ききできるかどうか判定しなさい。

アルゴリズム

強連結成分分解で、グラフが複数に分解されなければ１。
それ以外は０と答えました。
強連結成分分解については、アリ本P267などを参照してください。

プログラム

アリ本のコードを引用しているので、強連結成分分解のコードは、アリ本を参照してください。

int V,E;
vector<int> G[MAX_V];
vector<int> rG[MAX_V];
vector<int> vs;
bool used[MAX_V];
int cmp[MAX_V];

void init(){省略}
void add_edge(int from,int to){省略}
void dfs(int v){省略}
void rdfs(int v,int k){省略}
int scc(){省略}

int main(){
  while(cin>>V>>E,V||E){
    init();
    rep(i,E){
      int a,b,c;
      cin>>a>>b>>c;
      a--;
      b--;
      add_edge(a,b);
      if(c == 2){
        add_edge(b,a);
      }
    }
    cout<<(scc()==1 ? 1 : 0)<<endl;
  }
}