2014-08-01 Team Coding

Friends.java

import java.util.*;

/**
 * Created by woody on 7/31/14.
 */
public class Friends {
	private static int P, m, M, n, N;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		String str = scanner.nextLine();
		String[] parts = str.split(" ");
		P = Integer.parseInt(parts[0]);
		m = Integer.parseInt(parts[1]);
		M = Integer.parseInt(parts[2]);
		n = Integer.parseInt(parts[3]);
		N = Integer.parseInt(parts[4]);

		// Read the name. Assign a unique number for each name.
		Map<String, Integer> nameMap = new HashMap<String, Integer>();
		for (int i = 0; i < m; i++) {
			String name = scanner.nextLine();
			nameMap.put(name, i);
		}

		// Initializing...
		// I assume that any two people is not friends at first.
		boolean[][] friendsMap = new boolean[m][m];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				friendsMap[i][j] = false;
			}
		}

		for (int i = 0; i < M; i++) {
			String name1 = scanner.next();
			String name2 = scanner.next();
			scanner.nextLine();
			int id1 = nameMap.get(name1);
			int id2 = nameMap.get(name2);
			friendsMap[id1][id2] = true;
			friendsMap[id2][id1] = true;
		}

		boolean hasChanged;
		do {
			hasChanged = false;
			for (int i = 0; i < m - 1; i++) {
				for (int j = i + 1; j < m; j++) {
					boolean willBeFriends = false;
					if (getCountOfCommonFriends(friendsMap, i, j) > P) {
						willBeFriends = true;
					}
					if (!friendsMap[i][j] && willBeFriends) {
						hasChanged = true;
						friendsMap[i][j] = friendsMap[j][i] = true;
					}
				}
			}
		} while (hasChanged);

		for (int i = 0; i < n; i++) {
			String name = scanner.nextLine();
			if (!nameMap.containsKey(name)) {
				System.out.println("-1");
				continue;
			}
			int id = nameMap.get(name);
			System.out.println(getFriends(friendsMap, id).size());
		}

		for (int i = 0; i < N; i++) {
			String name1 = scanner.next();
			String name2 = scanner.next();
			scanner.nextLine();
			int id1 = nameMap.get(name1);
			int id2 = nameMap.get(name2);

			if (friendsMap[id1][id2]) {
				System.out.println("0");
			} else {
				System.out.println("-1");
			}
		}
	}

	private static Set<Integer> getFriends(boolean[][] friendsMap, int id) {
		Set<Integer> friends = new HashSet<Integer>();
		for (int i = 0; i < m; i++) {
			if (id != i && friendsMap[id][i]) {
				friends.add(i);
			}
		}
		return friends;
	}

	private static int getCountOfCommonFriends(boolean[][] friendsMap, int id1, int id2) {
		Set<Integer> friends1 = getFriends(friendsMap, id1);
		Set<Integer> friends2 = getFriends(friendsMap, id2);

		int count = 0;
		for (int id: friends1) {
			if (friends2.contains(id)) {
				count ++;
			}
		}
		return count;
	}
}