Skip to Content
CTRL K

Bipartiteness

Editorial oficial 

Explicación

Dada la cantidad de nodos coloreados y no coloreados, el máximo número de aristas que puede existir es c⋅ucc \cdot uc, donde cc representa el número de nodos coloreados y ucuc el número de nodos no coloreados.

Esto se debe a que se puede trazar una arista desde cada nodo coloreado hacia todos los nodos no coloreados. Sin embargo, ya tenemos n−1n - 1 aristas, así que la respuesta es (c⋅uc)−(n−1)(c \cdot uc) - (n - 1).

Para hallar el número de nodos coloreados y no coloreados, podemos ejecutar un DFS, incrementando el número de nodos coloreados y no coloreados a medida que recorremos el grafo.

Implementación

Complejidad temporal: O(N+M)\mathcal{O}(N + M)

#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
long long c = 0;
long long uc = 0;
 
void dfs(int node, int parent, bool col) {
	(col ? c : uc)++;
 
	for (int u : adj[node]) {
		// if the adjacent node isn't the parent,
		// visit that node with the opposite color
		if (u != parent) { dfs(u, node, !col); }
	}
}
 
int main() {
	int n;
	cin >> n;
 
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
 
	dfs(1, 0, 0);
 
	cout << c * uc - (n - 1) << endl;
}
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 {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
 
		// +1 for 1-indexed nodes
		adj = new ArrayList[n + 1];
 
		for (int i = 0; i <= n; i++) { adj[i] = new ArrayList<>(); }
 
		for (int i = 0; i < n - 1; i++) {
			int u = io.nextInt();
			int v = io.nextInt();
 
			adj[u].add(v);
			adj[v].add(u);
		}
 
		dfs(1, 0, false);
 
		// ans = (all possible edges) - (existing edges)
		long ans = (count[0] * count[1]) - (n - 1);
 
		io.println(ans);
		io.close();
	}
 
	public static void dfs(int node, int parent, boolean color) {
		count[color ? 0 : 1]++;
 
		for (int u : adj[node]) {
			// if the adjacent node isn't the parent,
			// visit that node with the opposite color
			if (u != parent) { dfs(u, node, !color); }
		}
	}
 
	// CodeSnip{Kattio}
}
# 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,
	using that still causes the stack to overflow.
	"""
	stack = [(node, parent, col)]
	while stack:
		node, parent, col = stack.pop()
 
		if col:
			c += 1
		else:
			uc += 1
 
		for u in adj[node]:
			# if the adjacent node isn't the parent,
			# push it onto the stack with the opposite color
			if u != parent:
				stack.append((u, node, not col))
 
 
n = int(input())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	u, v = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
 
dfs(1, 0, False)
 
print(c * uc - (n - 1))
Fundamentos