Indeedなう（予選B） C: 木

問題

C: 木 - Indeedなう（予選B） | AtCoder

解法

やるだけ。やるだけだけどnew int[100000][100000]はMLEするので、別の方法を考える。

コード

import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) {
		int N = nextInt();

		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < (N - 1); i++) {
			int a = nextInt() - 1;
			int b = nextInt() - 1;
			list.get(a).add(b);
			list.get(b).add(a);
		}

		PriorityQueue<Integer> queue = new PriorityQueue<>();
		queue.add(0);

		int cnt = 0;
		boolean[] checked = new boolean[N];
		checked[0] = true;
		while (!queue.isEmpty()) {
			int poll = queue.poll();
			System.out.print(poll + 1);
			cnt++;
			if (cnt != N) {
				System.out.print(" ");
			}

			for (Integer i : list.get(poll)) {
				if (!checked[i]) {
					queue.add(i);
					checked[i] = true;
				}
			}

		}
		System.out.println();
	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}

}