Submission #57569

---

Source Code Expand

import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N, M;
	static long E;
	static StringBuilder out = new StringBuilder();
	static BitSet[] g;

	public static void main(String[] args) {
		N = sc.nextInt();
		M = sc.nextInt();
		E = ((long) N) * (N - 1) / 2;
		if (E - M > N - 1) {
			for (int i = 0; i < M; ++i) {
				out.append("no\n");
			}
			System.out.print(out);
			return;
		}
		g = new BitSet[N];
		for (int i = 0; i < N; ++i) {
			g[i] = new BitSet(N);
			g[i].set(0, N);
			g[i].clear(i);
		}
		for (int i = 0; i < M; ++i) {
			int S = Integer.parseInt(sc.next()) - 1;
			int T = Integer.parseInt(sc.next()) - 1;
			g[T].set(S, !g[S].get(T));
			g[S].set(T, !g[S].get(T));
			if (g[S].get(T)) {
				++E;
			} else {
				--E;
			}
			out.append(calc() ? "yes\n" : "no\n");
		}
		System.out.print(out);
	}

	static boolean calc() {
		if (E > N - 1) return false;
		if (E <= 2) return true;
		boolean[] used = new boolean[N];
		for (int i = 0; i < N; ++i) {
			if (used[i]) continue;
			used[i] = true;
			if (!dfs(i, -1, used)) {
				return false;
			}
		}
		return true;
	}

	static boolean dfs(int pos, int from, boolean[] used) {
		for (int i = g[pos].nextSetBit(0); i >= 0; i = g[pos].nextSetBit(i + 1)) {
			if (i == from) continue;
			if (used[i]) return false;
			used[i] = true;
			if (!dfs(i, pos, used)) {
				return false;
			}
		}
		return true;
	}
}

Submission Info

Judge Result