AOJ-1055: Huge Family

keyword

最小全域木　Java

問題概要

ノード数N(<10^5)、全てのノードに関して接続次数2の重み付き無向グラフが与えられる。最小全域森が何種類できるか求める問題。

解法

接続次数が2の時点で環状になることが分かる。部分的な最小全域木は重み最大の辺を1本だけ辺を取り除いたものになる。なので重み最大の辺がいくつあるか数えるだけ。グラフの探索にDFSをやるとstack overflowした。Cだと10^6のオーダーまで大丈夫だと聞いていたんだけど、Javaだと色々あるんでしょう。

感想

自分は再帰関数の展開が苦手らしい。

import java.util.*;

public class Main {

	int[][] graph;
	int[][] weight;
	int maxValue, maxCnt;
	int N;
	boolean[] visited;
	static final int MOD = 10007;
	
	void run(){
		Scanner in = new Scanner(System.in);
		for(;;){
			N = in.nextInt();
			if(N == 0) return ;
			graph = new int[N][2];
			weight = new int[N][2];
			visited = new boolean[N];
			for(int i=0; i<N; i++){
				for(int j=0; j<2; j++){
					int x = Integer.parseInt(in.next()), fx = Integer.parseInt(in.next());
					graph[i][j] = x;
					weight[i][j] = fx;
				}
			}
			System.out.println(solve());
		}
	}

	int solve(){
		int ret = 1;
		for(int i=0; i<N; i++)if(!visited[i]){
			maxValue = weight[i][1]; maxCnt = 1;
			dfs(i);
			ret = (ret*(maxCnt%MOD))%MOD;
		}
		return ret;
	}

	void dfs(int v){
		for(;;){
			visited[v] = true;
			boolean end = true;
			for(int i=0; i<2; i++){
				if(!visited[graph[v][i]]){
					if(maxValue <= weight[v][i]){
						if(maxValue == weight[v][i]){
							maxCnt++;
						}
						else{
							maxValue = weight[v][i];
							maxCnt = 1;
						}
					}
					v = graph[v][i];
					end = false;
					break;
				}
			}
			if(end) return ;
		}
	}

	public static void main(String args[]){
		new Main().run();
	}
}