Codeforces Round #311 Div2 D: Vitaly and Cycle

問題

codeforces.com

解法

kmjp.hatenablog.jp

コード

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	private HashSet<Integer> black, white;

	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int M = scanner.nextInt();

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

		for (int i = 0; i < M; i++) {
			int x = scanner.nextInt() - 1;
			int y = scanner.nextInt() - 1;
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		scanner.close();

		// コーナーケース
		if (M == 0) {
			// 辺が1本もない時
			System.out.println("3 " + ((long) N * (N - 1) * (N - 2) / 6));
			return;
		}

		// すべての頂点の次数が1以下の時、辺が1本ずつバラバラになっているのでそれを拾う
		for (int i = 0; i < N; i++) {
			if (graph.get(i).size() >= 2) {
				break;
			}
			if (i == N - 1) {
				System.out.println("2 " + ((long) M * (N - 2)));
				return;
			}
		}

		// 二部グラフになっているかどうか
		long ans = 0;
		int[] color = new int[N];
		black = new HashSet<>();
		white = new HashSet<>();
		for (int i = 0; i < N; i++) {
			if (color[i] == 0) {
				black.clear();
				white.clear();
				if (!colorDFS(i, 1, color, graph)) {
					// 二部グラフじゃなければ奇数長の閉路があるぞい
					System.out.println("0 1");
					return;
				}

				// 連結成分内で、黒同士、あるいは、白同士の頂点を結ぶ
				long b = black.size();
				long w = white.size();
				ans += b * (b - 1) / 2;
				ans += w * (w - 1) / 2;
			}
		}

		System.out.println("1 " + ans);

	}

	private boolean colorDFS(int v1, int c, int[] color, ArrayList<ArrayList<Integer>> graph) {
		color[v1] = c;
		if (c > 0) {
			black.add(v1);
		} else {
			white.add(v1);
		}

		for (int v2 : graph.get(v1)) {
			if (color[v2] == c) {
				// 同じ色が連結してたらダメ
				return false;
			}
			if (color[v2] == -c) {
				// 既に塗り終わってたらok
				continue;
			}
			if (!colorDFS(v2, -c, color, graph)) {
				// まだ塗ってなかったら、こいつについてDFSして、そこでダメだったら終了
				return false;
			}
		}
		// 問題なければ正常終了
		return true;

	}

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