3475251_wa.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 59 行

import java.util.*;

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

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

	private void dfs(int v, int step) {
		
		boolean isleaf = true;

		if (win) {
			return ;
		}
		visited[v] = true;
		for (int i = 0; i < n; i++) {
			if (tree[v][i] && !visited[i]) {
				isleaf = false;
				dfs(i, step + 1);
			}
		}
		if (isleaf) {
			win = (step % 2 == 1);
		}
	}

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

		n = in.nextInt();
		k = in.nextInt() - 1;
		visited = new boolean [n];
		tree = new boolean [n][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;
		}
		win = false;
		visited[k] = true;
		for (int i = 0; i < n; i++) {
			if (tree[k][i]) {
				dfs(i, 1);
				if (win) {
					System.out.println("First player wins flying to airport " + (i + 1));
					return ;
				}
			}
		}
		System.out.println("First player loses");
	}
}