Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-29SRM357 (Practice)

SRM 357 WebsiteRank

|  SRM 357 WebsiteRank - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 357 WebsiteRank - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6406

  • めちゃくちゃ簡単なのに解けなかった、(自分に対して)訴訟
    • 素直に実装するだけ
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class WebsiteRank {

	boolean[][] graph, link;
	int len;
	
	public long countVotes(String[] votes, String website) {
		Map<String, Integer> namemap = new HashMap<String, Integer>();
		for (String v : votes) {
			String[] data = v.split(" ");
			int l = data.length;
			for (int i = 0 ; i < l ; i++) {
				if (!namemap.containsKey(data[i])) {
					namemap.put(data[i], namemap.size());
				}
			}
		}
		
		len = namemap.size();
		graph = new boolean[len][len];
		link = new boolean[len][len];
		for (String v : votes) {
			String[] data = v.split(" ");
			int l = data.length;
			int toid = namemap.get(data[0]);
			for (int i = 1 ; i < l ; i++) {
				int fromid = namemap.get(data[i]);
				graph[fromid][toid] = true;
				link[fromid][toid] = true;
			}
		}
		
		for (int k = 0 ; k < len ; k++) {
			for (int i = 0 ; i < len ; i++) {
				for (int j = 0 ; j < len ; j++) {
					if (graph[i][k] && graph[k][j]) {
						graph[i][j] = true;
					}
				}
			}
		}
		
		int[] indeg = new int[len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (link[i][j] && graph[j][i]) {
					link[i][j] = false;
				}
			}
		}

		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (link[i][j]) {
					indeg[j]++;
				}
			}
		}
		
		long[] val = new long[len];
		Arrays.fill(val, 1);
		
		while (true) {
			boolean done = false;
			for (int i = 0 ; i < len ; i++) {
				if (indeg[i] == 0) {
					for (int j = 0 ; j < len ; j++) {
						if (link[i][j]) {
							done = true;
							link[i][j] = false;
							indeg[j]--;
							val[j] += val[i];
						}
					}
				}
			}
			if (!done) {
				break;
			}
		}
		return val[namemap.get(website)];
	}
}