3475332_ac_2329ms_5676k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;
	private int n, k;
	private boolean [][] tree;
	private boolean [] visited;
	private boolean [] win;
	private int [] queue;
	private int [] father;
	private int front, rear;

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

	private void bfs() {

		front = -1;
		rear = -1;
		queue[++rear] = k;
		visited[k] = true;
		father[k] = -1;
		while (front < rear) {
			++front;
			int v = queue[front];
			for (int i = 0; i < n; i++) {
				if (tree[v][i] && !visited[i]) {
					visited[i] = true;
					queue[++rear] = i;
					father[i] = v;
				}
			}
		}
	}

	public void solve() {
		int to = -1;

		for (int i = rear; i >= 0; i--) {
			int v = queue[i];
			win[v] = false;
			for (int j = 0; j < n; j++) {
				if (!tree[v][j] || j == father[v]) {
					continue;
				}
				if (win[j] == false) {
					win[v] = true;
					to = j + 1;
					break;
				}
			}
		}
		if (win[k]) {
			System.out.println("First player wins flying to airport " + to);
		} else {
			System.out.println("First player loses");
		}
	}

	public void run() {
		in = new Scanner (System.in);

		n = in.nextInt();
		k = in.nextInt() - 1;
		visited = new boolean [n];
		queue = new int [n];
		tree = new boolean [n][n];
		father = new int [n];
		win = new boolean [n];
		for (int i = 1; i < n; i++) {
			int u, v;
			u = in.nextInt() - 1;
			v = in.nextInt() - 1;
			tree[u][v] = tree[v][u] = true;
		}
		bfs();
		solve();
	}
}