# Componentes (fuertemente) conexas
:::spoiler Prerequisitos
- DFS y representación de grafos
:::
## Componentes conexas
Una **componente conexa** en un grafo no dirigido **G** es un subconjunto de nodos **S** tal que para todo **u**, **v** en **S** existe un camino utilizando las aristas de **G** entre ****u**** y ****v****.
A continuación se presenta un ejemplo de un grafo con 3 componentes conexas (marcadas con distinto color). Se puede observar que existe un camino entre cada par de nodos pertenecientes a la misma componente.
Si quisiéramos saber el número de componentes distintas en un grafo no dirigido, “coloreando” cada componente con un color distinto, se puede utilizar el siguiente código:
```cpp
void dfs(int u, int color, vector<int>& colors) {
colors[u] = color;
for(int v : adj[u]) if(!colors[v]) {
dfs(v, color, colors);
}
}
int number_of_components() {
int n = adj.size();
vector<int> colors(n);
int color = 1;
int number = 0;
for(int u = 0; u < n; u++) if(!colors[u]) {
number++;
dfs(u, color++, colors);
}
return number;
}
```
La complejidad de esta implementación es $O(V + E)$, dado que solo hacemos una DFS.
## Componentes fuertemente conexas
Cuando se tiene un grafo dirigido $G$, se dice que un subgrafo $C_i$ es una componente fuertemente conexa de $G$ si para todo nodo $u$, $v$ en $C_i$ existe un camino de $u$ a $v$ y a su vez existe un camino de $v$ a $u$ en $G$. En este caso, como las aristas son dirigidas, puede que exista un camino del nodo $u$ al nodo $v$ pero no uno de $v$ a $u$.Como ejemplo de esto en la siguiente figura podemos ir de $4$ a cualquiera de los otros nodos, pero el caso contrario no se cumple, ya que para los nodos $1$, $2$ y $3$ no existe un camino de los mismos a $4$, por lo que en el grafo d ejemplo tenemos 2 componentes fuertemente conexas (marcadas en rojo y verde):
Se puede ver que las componentes fuertemente conexas de un grafo no se intersectan, por lo que se define el grafo de condensación $G^{scc}(P,Q)$ de $G(E, V)$, como un grafo que contiene como nodos cada componente fuertemente conexa de $G$. Existirá una arista entre los nodos $C_i, C_j \in Q$, si y sólo si existen nodos $u,v \in V$ tal que $u\in C_i$, $v\in C_j$ y $u \to v \in G$. El grafo $G^{scc}$ cumple con la propiedad de ser acíclico. El grafo de condensación de nuestro ejemplo se muestra a continuación
Supongamos que nuestro grafo condensado no es acíclico, entonces existen 2 componentes distintas $C_i$ y $C_j$ tales que el camino $C_i \to C_j$ y el camino $C_j \to C_i$ existen. Esto quiere decir que $\forall u \in C_i, v\in C_j$ los caminos $u \to v, v \to u$ existen. Pero la definición de componente conexa nos dice que si para dos nodos $u,v$ existen los caminos $u \to v$ y $v\to u$ en el grafo original, entonces $u,v$ pertenecen a la misma componente conexa, lo cual contradice nuestra proposición original de que $C_i \neq C_j$, por lo tanto el grafo condensado es acíclico.
---
La manera de obtener componentes fuertemente conexas no es tan trivial como en el caso de los grafos no dirigidos. Para grafos dirigidos existen distintos algoritmos:
- Algoritmo de Kosaraju
- Algoritmo de Tarjan
- Path based algorithm
### Algoritmo de Kosaraju
Este algoritmo se basa en el hecho de que el grafo condensado $G^{scc}$ de un grafo $G$, es dirigido acíclico, es decir, tiene un [topological sort](https://en.wikipedia.org/wiki/Topological_sorting#:~:text=Precisely%2C%20a%20topological%20sort%20is,directed%20acyclic%20graph%20(DAG).).
Definamos el grafo transpuesto $G^T$ de $G$ como un grafo que tiene los mismos nodos que $G$, pero sus aristas invertidas, es decir, si la arista $(u,v)$ existe en $G$, entonces $(v,u)$ existe en $G^T$. Es fácil ver que los grafos $G$ y $G^T$ tienen las mismas componentes conexas, mientras que el grafo $G^{scc_T}$ tendra el mismo número de nodos que $G^{scc}$ pero con las aristas invertidas.
Con base en la idea de que el topological sort nos entrega un ordenamiento en el que, si existe un camino $u \to v$, para cualesquiera $u,v$, entonces $u$ debe de aparecer antes que $v$ en el ordenamiento; si se realiza una serie de dfs's siguiendo este orden en el grafo $G^{T}$, entonces un nodo $u$ solo podrá visitar a los nodos que pertenecen a la misma componente fuertemente conexa.
El algoritmo es el siguiente:
- Obtener el ordenamiento necesario. Es aquel en el que si la arista $u \to v$ existe, entonces $u$ debe ir antes de $v$, por lo que si realizamos una dfs llamando recursivamente a la misma en los nodos adyacentes a $u$ y luego metemos $u$ obtendremos el ordenamiento necesario pero invertido.
- Por cada nodo $u$ en el ordenamiento que no ha sido visitado, realizar una dfs guardando los nodos que se visitan durante la misma (estos pertenecen a la misma componente).
- Si deseamos generar el grafo $G^{scc}$ tenemos que llevar un nodo "representante" de cada componente, el cuál decimos que es la raíz de nuestra componente y marcar todos los nodos en la misma con esta raíz.
- Finamente, por cada arista $(u,v)$ en $G$ si $root[u] \neq root[v]$ entonces en $G^{scc}$ existira la rista $(root[u], root[v])$
:::spoiler Implementación en C++
```c++
#include<bits/stdc++.h>
#define lli long long int
#define ld long double
#define forn(i,n) for(int i = 0; i < n; i++)
#define forr(i,a,n) for(int i = a; i <= n; i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define endl '\n'
#define fastIO() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<lli> vlli;
vector<int> order;
struct Graph {
int V;
vector<vi> adj;
Graph() {}
Graph(int n) : adj(n), V(n) {}
void addEdge(int u, int v, bool dir = false) {
adj[u].pb(v);
if(!dir) adj[v].pb(u);
}
pair<Graph, vi> kosaraju() {
vector<bool> vis(V);
vector<int> order;
vector<vi> adj_t(V);
// creamos la lista de adyacencia transpuesta
forn(u,V) for(int v : adj[u]) adj_t[v].pb(u);
// Despues de realizar esta dfs obtendremos el orden deseado
// en este caso, obtenemos un orden llamado "topological sort"
// en reversa
auto dfs1 = [&](const auto& dfs1, int u) -> void {
vis[u] = true;
for(int v : adj[u]) if(!vis[v])
dfs1(dfs1, v);
order.pb(u);
};
// Con esta dfs obtenemos los elementos de la componente
// conexa que estamos calculando, es importante notar que
// usamos grafo transpuesto en esta dfs
auto dfs2 = [&](const auto& dfs2, int u, vi& component) -> void {
vis[u] = true;
component.pb(u);
for(int v : adj_t[u]) if(!vis[v])
dfs2(dfs2, v, component);
};
forn(u,V) if(!vis[u]) dfs1(dfs1, u);
// La primer dfs nos devuelve el topological sort al reves
reverse(all(order));
fill(all(vis), false); // Reseteamos los visitados
vector<int> roots(V); // Los representantes de la componente
vector<vector<int>> components;
for(int u : order) {
if(vis[u]) continue;
vi component;
dfs2(dfs2, u, component);
// Aqui se puede hacer lo que sea con la componente
int root = component.front();
for(int v : component) roots[v] = root;
components.pb(component);
}
Graph g_scc(V);
forn(u,V) {
int root_u = roots[u];
for(int v : adj[u]) {
int root_v = roots[v];
// Esto puede generar aristas duplicadas,
// aunque la mayoria del tiempo no causan
// problema es algo a tener en cuenta
if(root_u != root_v)
g_scc.addEdge(root_u, root_v);
}
}
return {g_scc, roots};
}
};
void solve() {
int n, m;
cin >> n >> m;
Graph g(n);
forn(i,m) {
int u, v;
cin >> u >> v;
u--, v--;
g.addEdge(u,v,true);
}
auto[g_scc, roots] = g.kosaraju();
forn(u,n) cout << "roots[" << u << "] = " << roots[u] << endl;
}
int main() {
fastIO();
int tt = 1;
//cin >> tt;
while(tt--)
solve();
return 0;
}
```
:::
:::spoiler Ejemplo del algoritmo
En la siguiente serie de imágenes podemos ver un ejemplo de la dfs para obtener el orden de los nodos, cuando un nodo es coloreado de verde quiere decir que ya fue completamente procesado, cuando está de amarillo aún faltan nodos en su lista de adyacencia por visitar.
Ya con el orden obtenido (notar que está en el orden inverso al que necesitamos), procedemos a obtener las componentes conexas. En la siguiente serie de diagramas se muestra el proceso de dfs en el que se forman las componentes fuertemente conexas.
:::
:::spoiler **¿Por qué funciona si el topological sort sirve cuando no hay ciclos en el grafo?**
Para este algoritmo, lo que nos importa es obtener un topological sort del grafo $G^{scc}$ (aunque el mismo no haya sido construido aún), ya que esto es lo que nos permite decir que durante la segunda dfs, $dfs(u)$ solo va a visitar a los nodos de la componente fuertemente conexa de $u$, debido a:
- $G^{scc}$ es un grafo acíclico, por lo que existe un topological sort para el mismo, digamos que existe la arista $C_i \to C_j$ en $G^{scc}$, entonces, en el topological sort, $C_i$ debe ir antes que $C_j$. Sabiendo esto, si hacemos una dfs en el grafo $G^{T}$ comenzando en un nodo $u \in C_i$, es imposible que esta dfs alcance a cualquier elemento de $C_j$ (si suponemos lo contrario esto implicaría la existencia de la arista $C_j \to C_i \in G^{scc}$ lo cual forma un ciclo y eso es imposible) por lo que sólo se visitan los nodos de la componente conexa de $u$, y al ser marcados como visitados ya no son considerados para futuras dfs's.
Ahora sólo nos resta comprobar que la dfs nos va a entregar un topological sort válido, es decir que si $C_i \to C_j \in G^{scc}$ entonces $C_i$ aparece antes que $C_j$ en el ordenamiento.
Sea $tout[u]$ el índice que se le asigna a $u$ una vez que todos los nodos en su lista de adyacencia han sido procesados. Para que un nodo $u$ aparezca antes que $v$ en el topological sort de un grafo ac, entonces $tout[u] > tout[v]$.
Decimos que $tout[C_i]$ es el mayor índice asignado a cualquier $v \in C_i$. Probar que $tout[C_i] > tout[C_j]$ si la arista $C_i \to C_j \in G^{scc}$, nos ayuda a probar que la primer dfs genera un ordenamiento valido, ya que esto implica que todos los nodos de la componente $C_j$ son procesados antes que los de $C_i$, por lo que al ordenar los nodos $u\in G$ por su valor de $tout$ de manera decreciente nos da como resultado que existe al menos un nodo $u \in C_i$ tal que $u$ aparece antes que cualquier nodo en $C_j$ y esto a su vez prueba que si hacemos $dfs(u)$ en $G^{T}$ se visitan a todos los nodos de $C_i$, sin poder visitar los de $C_j$ (ya que la arista $C_i \to C_j$ está invertida).
Para probar que $tout[C_i] > tout[C_j]$ si la arista $C_i \to C_j \in G^{scc}$ se tienen 2 casos:
- Si $C_i$ es visitada (pero no totalmente procesada) antes que $C_j$, entonces nos encontramos procesando un nodo $v \in C_i$, como existe la arista $(Ci, C_j)$, entonces todos los nodos $w \in C_j$ pueden alcanzarse desde $v$, lo que implica que van a terminar de ser procesados antes que $v$, entonces $tout[v] > tout[w]$.
- Si $C_j$ es visitada antes que $C_i$, entonces visitaremos a todos los nodos de $C_j$, y como la arista $C_i \to C_j$ existe en $G^{scc}$, entonces por las propiedades de éste (es un grafo acíclico) no hay forma de llegar a los nodos de $C_i$, por lo que $tout[C_i] > tout[C_j]$
:::
<!-- ## Problemas
:::spoiler [Checkposts](https://codeforces.com/problemset/problem/427/C)
Dado un grafo con **n** nodos, donde cada nodo **i** cuesta ********a[i]********, y un conjunto de aristas entre los mismos de tamaño **m**. Encontrar el número de subconjuntos de los **n** nodos tal que los nodos en el subconjunto “vigilen” a todos los demás, el costo del mismo sea el mínimo posible y la cardinalidad del subconjunto sea mínima.
- Un nodo ****u**** vigila a un nodo ****v**** si existe un camino de ****u**** a **v** y de regreso, y **u** es un “vigilante”.
- El costo del conjunto de nodos es igual a la suma de los costos de cada uno de los nodos “vigilantes”.
- La cardinalidad de un subconjunto es el número de elementos en el mismo
**Cotas**
$$
1 \leq n \leq 10^5\\
0 \leq m \leq 3\times10^5 \\
0 \leq a[i] \leq 1e9
$$
**Salida**
- El costo mínimo posible y el número de subconjuntos distintos que dan el mínimo posible.
**Solución**
Con el siguiente caso de ejemplo
```jsx
5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1
```
Se forma este grafo
Veamos lo que pasa si escogemos algunos subconjuntos de nodos.
- Si escogemos los nodos de color verde en la figura que se muestra a continuación estaremos cumpliendo la condición que dice que el subconjunto elegido debe de cubrir todos los nodos, pero no se cumple que la suma de los costos de los nodos en el conjunto sea mínima (podemos eliminar el nodo 1 del conjunto y la primer condición se sigue cumpliendo, mientras el costo baja).
- Por otro lado, si escogemos el subconjunto ****{3,5}****, tendremos un costo muy bajo, pero no se cumple la condición de vigilar todos los nodos ya que el nadie vigila al nodo **2**.
- Si escogemos los nodos ****{5,3,2}**** tendremos un subconjunto con costo mínimo, que vigila a todos los nodos, pero que no es de la mínima cardinalidad, ya que si quitamos al nodo **5**, se siguen cumpliendo las otras 2 condiciones.
- La respuesta óptima es escoger **{5,2}** o **{3,2}**.
por lo que la respuesta es `8 2`.
**Observaciones:**
::: -->
Sign in with Wallet
Connect another wallet