１１７ C Cycle - simezi

問題

トーナメントであるグラフとは、どの二つの頂点u,vも、u,vの間にちょうど一本の辺(u,v)または(v,u)があるようなグラフを言う。

n頂点からなるトーナメントなグラフが与えられるとき、このグラフが長さ3の閉路をもつならば、その3つの頂点を出力し、そうでなければ-1を出力せよ。

制約条件

n≦5000

方針

少し考えると、トーナメントなグラフが長さ4以上の閉路を持つとき、そのグラフは長さ3の閉路を必ず持つことがわかる。
例えば、
v1→v2→v3→v4→v5→v6→v1みたいな閉路があった場合、
v1とv3には辺があるはずで、v1→v3の向きだったらv4→v5→v6→v1が閉路に、
v3→v1の向きだったらv1→v2→v3が閉路になる。

これを長い閉路にどんどん適用していくと長さ3の閉路が得られる。

ということで、ループを検出して、
v1→v2→v3→v4→v5→v6→v1みたいなループがあった場合、

(v1,v2)を含む長さ3の閉路
(v2,v3)を含む長さ3の閉路
(v3,v4)を含む長さ3の閉路
(v4,v5)を含む長さ3の閉路
(v5,v6)を含む長さ3の閉路
(v6,v1)を含む長さ3の閉路

のいずれかがある。
のでそれを全部見てやる。

ループの検出にはDFSを一度やればいいのでO(n).
ループが一度検出されたら、ループの、
それぞれの辺について、それを含むような長さ3の閉路があるかを調べる。これにO(n^2)かかる。
ので、全体の計算量はO(n^2)となる。

ソースコード

int n,visit[5000],prev[5000];
bool e[5000][5000],found;

void rec(int c){
  visit[c]=1;
  if(found)return;
  rep(i,n)if(e[c][i]){
    if(visit[i]==1){
      found=1;
      vi v; v.pb(i);
      for(;c!=i;c=prev[c])v.pb(c);
      v.pb(i);
      rep(j,v.size()-1)rep(k,n)if(e[v[j]][k]&&e[k][v[j+1]]){
        cout<<v[j]+1<<" "<<k+1<<" "<<v[j+1]+1<<endl;
        return;
      }
    }
    else if(visit[i]==0){
      prev[i]=c; rec(i);
      if(found)return;
    }
  }
  visit[c]=2;
}
void run(){
  scanf("%d",&n);
  rep(i,n){
    char in[5001]; scanf("%s",in);
    rep(j,n)e[i][j]=in[j]=='1';
    visit[i]=0; prev[i]=-1;
  }
  found=0;
  rep(i,n)if(!visit[i]){
    rec(i);
    if(found)return;
  }
  cout<<-1<<endl;
}