Table of Contents

ExplanationImplementation

Official Editorial

Explanation

Given the number of colored and uncolored nodes, the maximum number of edges that can exist is c⋅ucc \cdot uc where cc represents the number of colored nodes, and ucuc represents the number of uncolored nodes.

This is because an edge can be drawn from each colored node to every other uncolored node. However, we already have n−1n - 1 edges, so the answer is (c⋅uc)−(n−1)(c \cdot uc) - (n - 1).

To find the number of colored and uncolored nodes, we can run a DFS, incrementing the number of colored and uncolored nodes as we traverse the graph.

Implementation

Time Complexity: O(N+M)\mathcal{O}(N + M)

C++

#include <iostream>
#include <vector>
using namespace std;


const int MAX_N = 100000;


// +1 for 1-indexed nodes
vector<int> adj[MAX_N + 1];


// counters for colored and uncolored nodes

Java

import java.io.*;
import java.util.*;


public class Bipartiteness {
	public static ArrayList<Integer>[] adj;


	// counters for colored and uncolored nodes
	public static long[] count = {0, 0};


	public static void main(String[] args) throws IOException {

Python

# counters for colored and uncolored nodes
c = 0
uc = 0




def dfs(node: int, parent: int, col: bool) -> int:
	global c, uc
	"""
	Iteratively DFS with a stack.
	While we can increase the recursion depth with sys.setrecursionlimit,

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum