Connected Components?

Solución 1 - DFS más rápido

Hacer un DFS estándar sería demasiado lento. Puede haber como máximo $\frac{N(N-1)}2$ aristas, lo que daría complejidad $\mathcal{O}(N^2)$ . Para acelerarlo, hay que hacer dos optimizaciones.

Optimización 1

Podemos guardar si las aristas no existen usando un arreglo de conjuntos hash en lugar de una lista de adyacencia. Así podemos saber si no hay arista entre dos nodos en $\mathcal{O}(1)$ . Usar una matriz de adyacencia ocuparía demasiada memoria.

Optimización 2

En lugar de usar un arreglo booleano estándar para comprobar si un nodo aún no fue visitado, podemos usar un conjunto de nodos no visitados. Así solo recorremos los nodos que aún no fueron visitados y podemos hallar el siguiente nodo no visitado en $\mathcal{O}(\log N)$ . Hay que usar upper_bound para hallar el siguiente nodo no visitado después de un DFS: un iterador puede invalidarse porque el nodo al que apunta se destruye cuando lo quitamos del conjunto de no visitados.

Demostración

Sabemos que un nodo o se salta o se visita. También sabemos que una vez que un nodo se visita, no se puede volver a visitar. Por lo tanto siempre visitaremos $N$ nodos una vez. También sabemos que la suma de saltos es a lo sumo $2M$ (cada no-arista salta dos nodos). Por lo tanto la complejidad total será $O(N\log N+M)$ .

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 200000;
unordered_set<int> adj[MAX_N];
set<int> unvis;  // the set of nodes that have not been visited
int sz[MAX_N];   // sz[i] = size of the ith connected component
int cur = 0;     // current amount of groups
void dfs(int x) {
	sz[cur]++;
	auto it = unvis.begin();
	while (it != unvis.end()) {
		// if there is no edge between x and *it, skip
		if (adj[x].count(*it)) {
			it++;
		} else {
			// there is a edge between last and x
			int last = *it;
			// note it = unvis.erase(it) doesn't work here because it could be
			// erased later
			unvis.erase(it);
			dfs(last);
			// find the node after last
			it = unvis.upper_bound(last);
		}
	}
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].insert(b);
		adj[b].insert(a);
	}
	for (int i = 0; i < n; i++) { unvis.insert(i); }
	for (int i = 0; i < n; i++) {
		auto it = unvis.find(i);
		if (it != unvis.end()) {
			unvis.erase(it);
			dfs(i);
			cur++;
		}
	}
	cout << cur << endl;
	sort(sz, sz + cur);
	for (int i = 0; i < cur; i++) { cout << sz[i] << ' '; }
	cout << endl;
}

Solución 2 - DFS selectivo

Sea $N =$ el número de nodos del grafo, $n =$ un nodo arbitrario y $\texttt{degree}(n)=$ el número de nodos vecinos (nodos conectados directamente con $n$ ).

Sabemos que el tamaño de la componente que contiene al nodo $n$ debe ser al menos $\texttt{degree}(n)+1$ ( $\texttt{degree}(n)$ no incluye a $n$ ).

Si $\texttt{degree}(n_1)+1>\dfrac{N}2$ y $\texttt{degree}(n_2)+1>\dfrac{N}2$ , $n_1$ y $n_2$ deben intersectarse; en caso contrario el grafo tendría más de $N$ nodos.

Con esto, podemos poner todos los nodos con $\texttt{degree} +1 > \dfrac{N}2$ en el mismo grupo en $O(N)$ .

Ahora procesamos con DFS todos los nodos con $\texttt{degree}+1\le\dfrac{N}2$ .

Demostración

Podemos tratar todos los nodos con $\texttt{degree}+1>\dfrac{N}2$ en $O(N)$ .

Sean $N'$ los nodos que tienen a lo sumo $\dfrac{N}2 -1 ≈ \dfrac{N}2$ aristas. Entonces también deben tener al menos $\dfrac{N}2$ no-aristas. Por lo tanto, debe haber al menos $\dfrac{N'\cdot\dfrac{N}2}2 = \dfrac{N\cdot N'}4$ no-aristas (cada arista cuenta para dos nodos).

La entrada indica que el número de aristas es menor que $2 \cdot 10^5$ , por lo tanto $\dfrac{N \cdot N'}4\le2\cdot10^5$ , por lo tanto $N \cdot N' \le8\cdot10^5$ .

Hacer un DFS simple y comprobar si dos nodos se intersectan sería $\mathcal{O}(NN'+ \log M)$ , lo que entra en el límite de tiempo. El $\log M$ viene de procesar la entrada. Por lo tanto, esto corre dentro del límite de tiempo.

Implementación

Complejidad temporal: $\mathcal{O}(NN'+ \log M)$

C++


#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
 
const int MAX_N = 200000;
unordered_set<int> adj[MAX_N];
// group[i] = the group of the ith node
// group[i] = 0 if the ith node hasn't been assigned a group yet
int group[MAX_N];
vi currentcomponent;  // the nodes in the current component
// curgroup = the group of the current component
// curgroup is always either cur or 1
int curgroup;
bool vis[MAX_N];
int n, m;
// sz[i] = size of group i
int sz[MAX_N];
 
void dfs(int x) {
	// if x can be reached, it is part of the current component
	currentcomponent.pb(x);
	vis[x] = true;
	for (int i = 0; i < n; i++) {
		// if there is no, non-edge between x and i, i can be visited
		if (x != i && adj[x].find(i) == adj[x].end()) {
			// if we can visit a node from group one every node in
			// the current component can visit group 1 and we don't
			// have to create a new component
			if (group[i] == 1) {
				curgroup = 1;
				continue;
			} else {
				if (!vis[i]) { dfs(i); }
			}
		}
	}
}
 
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		adj[a].insert(b);
		adj[b].insert(a);
	}
	int cur = 1;  // current number of groups + 1
	for (int i = 0; i < n; i++) {
		// if any two nodes have degree+1 > n/2, they are part of the same
		// component
		if (n - adj[i].size() > n / 2) {
			group[i] = 1;  // assign ith node to component 1
			sz[1]++;       // increase the size of component 1
 
			cur = 2;  // there is at least one group
		}
	}
	for (int i = 0; i < n; i++) {
		if (!group[i]) {
			// curgroup's default is cur
			curgroup = cur;
			dfs(i);
			for (int j : currentcomponent) {
				group[j] = curgroup;
				sz[curgroup]++;
			}
			currentcomponent.clear();
			// if a new group has been created, e.g. curgroup = cur, increase
			// cur
			if (curgroup == cur) { cur++; }
		}
	}
	cout << cur - 1 << endl;
	sort(sz, sz + cur);
	for (int i = 1; i < cur; i++) { cout << sz[i] << ' '; }
	cout << endl;
}