Codeforces Beta Round #95 (Div. 2) D : Subway

問題概要

ノード数V(<3000)、辺数Vの連結な無向グラフが与えられる。当然環状な部分が一つできるが、それを一つの頂点に潰したグラフで、潰した頂点からの各点への距離を全て求める問題。

解法

頂点を潰した後は木になるので距離は簡単に求められる。問題は環を潰す部分。次数1の頂点を見つけて減らしていけば残ったのが環になる。

本番で通ったコード

計算量O(V^2)。

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX_N = 3000;
const int INF = 1<<29;

int N;
vector<int> graph[MAX_N];
bool visited[MAX_N];
int degree[MAX_N];
int dist[MAX_N];


void solve(){

	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++)if(degree[j] == 1){
			for(int k=0; k<(int)graph[j].size(); k++){
				degree[graph[j][k]]--;
			}
			degree[j] = 0;
		}
	}

	fill(dist, dist + N, INF);
	queue<int> que;

	for(int i=0; i<N; i++)if(degree[i] > 0){
		dist[i] = 0;
		visited[i] = true;
		que.push(i);
	}

	while(!que.empty()){
		int v = que.front(); que.pop();
		for(int i=0; i<graph[v].size(); i++){
			int u = graph[v][i];
			if(!visited[u]){
				visited[u] = true;
				dist[u] = dist[v] + 1;
				que.push(u);
			}
		}
	}

	for(int i=0; i<N; i++){
		printf("%d%c", dist[i], i==N-1?'\n':' ');
	}
}

int main(){

	scanf("%d", &N);
	for(int i=0; i<N; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
		degree[x]++;
		degree[y]++;
	}

	solve();

	return 0;
}