Codeforces 131 D. Subway

問題

n個の頂点とn個の辺からなる連結な単純無向グラフが与えられる。
このグラフには閉路が一つだけ存在する。

それぞれの頂点の、閉路からの距離を求めよ。

制約条件

n≦3000

方針

深さ優先探索して、同じ頂点に戻ってきたら閉路が検出できる。

閉路を一つ見つけたら、閉路を構成する点を全部開始点にして、
適当に幅優先探索して距離を求める。

ソースコード

int n;
vector<vi> g;
int prev[3000],v,dist[3000];
bool dfs(int c,int p){
	//dbg(c);
	prev[c]=p;
	rep(i,g[c].size())if(g[c][i]!=p){
		if(prev[g[c][i]]!=-1){
			prev[g[c][i]]=c;
			v=c; return 1;
		}
		if(dfs(g[c][i],c))return 1;;
	}
	return 0;
}
void run()
{
	cin>>n;
	g=vector<vi>(n);
	rep(i,n){
		int a,b; cin>>a>>b;
		g[--a].pb(--b);
		g[b].pb(a);
	}
	memset(prev,-1,sizeof(prev));
	memset(dist,-1,sizeof(dist));
	dfs(0,-1);
	//rep(i,n)cerr<<prev[i]<<(i==n-1?"\n":" ");
	int p=v;
	queue<int> q;
	do{
		q.push(p);
		dist[p]=0;
		p=prev[p];
	}while(p!=v);
	while(!q.empty()){
		p=q.front(); q.pop();
		rep(i,g[p].size())if(dist[g[p][i]]==-1){
			dist[g[p][i]]=dist[p]+1;
			q.push(g[p][i]);
		}
	}
	rep(i,n)cout<<dist[i]<<(i==n-1?"\n":" ");
}