P8435 【Plantilla】Componentes Biconectos por Nodos
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 500005;
vector<int> grafo[MAXN];
vector<int> componentes[MAXN];
int orden[MAXN], bajo[MAXN], tiempo;
int pila[MAXN], tope, numComponentes;
int n, m;
void agregarArista(int u, int v) {
grafo[u].push_back(v);
grafo[v].push_back(u);
}
void tarjan(int nodo, int padre) {
int hijos = 0;
orden[nodo] = bajo[nodo] = ++tiempo;
pila[++tope] = nodo;
for (int vecino : grafo[nodo]) {
if (!orden[vecino]) {
hijos++;
tarjan(vecino, nodo);
bajo[nodo] = min(bajo[nodo], bajo[vecino]);
if (bajo[vecino] >= orden[nodo]) {
numComponentes++;
while (pila[tope + 1] != vecino)
componentes[numComponentes].push_back(pila[tope--]);
componentes[numComponentes].push_back(nodo);
}
} else if (vecino != padre)
bajo[nodo] = min(bajo[nodo], orden[vecino]);
}
if (padre == 0 && hijos == 0)
componentes[++numComponentes].push_back(nodo);
}
void resolver() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
agregarArista(u, v);
}
for (int i = 1; i <= n; i++)
if (!orden[i])
tope = 0, tarjan(i, 0);
cout << numComponentes << endl;
for (int i = 1; i <= numComponentes; i++) {
cout << componentes[i].size() << " ";
for (int nodo : componentes[i])
cout << nodo << " ";
cout << endl;
}
}
int main() {
resolver();
return 0;
}
</int></int></algorithm></stack></vector></iostream>
P8436 【Plantilla】Componentes Biconectos por Aristas
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 500010;
const int MAXM = 2000010 * 2;
int n, m;
vector<int> grafo[MAXN];
int orden[MAXN], bajo[MAXN], tiempo;
int pila[MAXN], tope;
int id[MAXN], numComponentes;
bool esPuerta[MAXM];
int tamano[MAXN];
vector<int> componentes[MAXN];
void agregarArista(int a, int b) {
grafo[a].push_back(b);
grafo[b].push_back(a);
}
void tarjan(int nodo, int desde) {
orden[nodo] = bajo[nodo] = ++tiempo;
pila[++tope] = nodo;
for (int i = 0; i < grafo[nodo].size(); i++) {
int vecino = grafo[nodo][i];
int idx = i * 2 + (nodo < vecino ? 0 : 1);
if (!orden[vecino]) {
tarjan(vecino, idx);
bajo[nodo] = min(bajo[nodo], bajo[vecino]);
if (bajo[vecino] > orden[nodo])
esPuerta[idx] = esPuerta[idx ^ 1] = true;
} else if (idx != (1 ^ desde))
bajo[nodo] = min(bajo[nodo], orden[vecino]);
}
if (orden[nodo] == bajo[nodo]) {
numComponentes++;
int y;
do {
y = pila[tope--];
id[y] = numComponentes;
} while (y != nodo);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
agregarArista(a, b);
}
for (int i = 1; i <= n; i++)
if (!orden[i]) tarjan(i, -1);
cout << numComponentes << endl;
for (int i = 1; i <= n; i++) {
tamano[id[i]]++;
componentes[id[i]].push_back(i);
}
int p = 1;
while (tamano[p]) {
cout << tamano[p] << " ";
for (int i = 0; i < componentes[p].size(); i++)
cout << componentes[p][i] << " ";
p++;
cout << endl;
}
return 0;
}
</int></int></cstring></vector></iostream>
P3388 【Plantilla】Puntos de Corte
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005;
int n, m, contador;
int orden[MAXN], bajo[MAXN], numHijos[MAXN];
bool esCorte[MAXN];
vector<int> grafo[MAXN];
void dfs(int nodo, int padre) {
orden[nodo] = bajo[nodo] = ++contador;
numHijos[nodo] = 0;
for (int vecino : grafo[nodo]) {
if (!orden[vecino]) {
numHijos[nodo]++;
dfs(vecino, nodo);
bajo[nodo] = min(bajo[nodo], bajo[vecino]);
if (padre != -1 && bajo[vecino] >= orden[nodo])
esCorte[nodo] = true;
} else if (vecino != padre)
bajo[nodo] = min(bajo[nodo], orden[vecino]);
}
if (padre == -1 && numHijos[nodo] > 1)
esCorte[nodo] = true;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
grafo[u].push_back(v);
grafo[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!orden[i])
dfs(i, -1);
int total = 0;
for (int i = 1; i <= n; i++)
if (esCorte[i]) total++;
cout << total << endl;
for (int i = 1; i <= n; i++)
if (esCorte[i]) cout << i << " ";
return 0;
}
</int></vector></iostream>
P3469 [POI 2008] BLO-Bloqueo
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005;
const int MAXM = 500005;
struct Arista {
int destino, siguiente;
};
int n, m;
vector<arista> aristas(MAXM);
vector<int> listaAdyacencia(MAXN);
int orden[MAXN], bajo[MAXN], tiempo;
int tamanoComponente[MAXN];
int resultado[MAXN];
void agregarArista(int u, int v) {
aristas.push_back({v, listaAdyacencia[u]});
listaAdyacencia[u] = aristas.size() - 1;
}
void dfs(int nodo) {
orden[nodo] = bajo[nodo] = ++tiempo;
tamanoComponente[nodo] = 1;
int suma = 0;
for (int i = listaAdyacencia[nodo]; i != -1; i = aristas[i].siguiente) {
int vecino = aristas[i].destino;
if (!orden[vecino]) {
dfs(vecino);
tamanoComponente[nodo] += tamanoComponente[vecino];
bajo[nodo] = min(bajo[nodo], bajo[vecino]);
if (bajo[vecino] >= orden[nodo]) {
resultado[nodo] += tamanoComponente[vecino] * suma;
suma += tamanoComponente[vecino];
}
} else {
bajo[nodo] = min(bajo[nodo], orden[vecino]);
}
}
resultado[nodo] += (n - suma - 1) * suma;
resultado[nodo] += n - 1;
}
int main() {
cin >> n >> m;
fill(listaAdyacencia.begin(), listaAdyacencia.begin() + n + 1, -1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
agregarArista(u, v);
agregarArista(v, u);
}
dfs(1);
for (int i = 1; i <= n; i++)
cout << resultado[i] * 2 << endl;
return 0;
}
</int></arista></vector></iostream>
P2860 [USACO06JAN] Rutas Redundantes G
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 5005;
const int MAXM = 100005;
int n, m;
vector<int> grafo[MAXN];
int orden[MAXN], bajo[MAXN], tiempo;
int pila[MAXN], tope;
int id[MAXN], numComponentes;
bool visitado[MAXM * 2];
int grado[MAXN];
int resultado;
void agregarArista(int u, int v) {
grafo[u].push_back(v);
grafo[v].push_back(u);
}
void tarjan(int nodo) {
orden[nodo] = bajo[nodo] = ++tiempo;
pila[++tope] = nodo;
for (int i = 0; i < grafo[nodo].size(); i++) {
int vecino = grafo[nodo][i];
int idx = i * 2 + (nodo < vecino ? 0 : 1);
if (!visitado[idx]) {
visitado[idx] = visitado[idx ^ 1] = true;
if (!orden[vecino]) {
tarjan(vecino);
bajo[nodo] = min(bajo[nodo], bajo[vecino]);
} else {
bajo[nodo] = min(bajo[nodo], orden[vecino]);
}
}
}
if (orden[nodo] == bajo[nodo]) {
numComponentes++;
int y;
do {
y = pila[tope--];
id[y] = numComponentes;
} while (y != nodo);
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
agregarArista(u, v);
}
for (int i = 1; i <= n; i++)
if (!orden[i]) tarjan(i);
for (int i = 1; i <= m; i++) {
int u = grafo[i/2][i%2];
int v = grafo[i/2][i%2^1];
if (id[u] != id[v]) {
grado[id[u]]++;
grado[id[v]]++;
}
}
for (int i = 1; i <= numComponentes; i++)
if (grado[i] == 1) resultado++;
cout << (resultado + 1) / 2 << endl;
return 0;
}
</int></cstring></vector></iostream>
P5058 [ZJOI2004] Detector de Olores
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 210000;
vector<int> grafo[MAXN];
int orden[MAXN], bajo[MAXN], paso;
int padre[MAXN], numHijos[MAXN];
bool esCorte[MAXN];
int inicio, fin;
void dfs(int nodo) {
orden[nodo] = bajo[nodo] = ++paso;
numHijos[nodo] = 0;
for (int vecino : grafo[nodo]) {
if (vecino == padre[nodo]) continue;
if (!orden[vecino]) {
padre[vecino] = nodo;
numHijos[nodo]++;
dfs(vecino);
if (bajo[vecino] >= orden[nodo] && orden[fin] >= orden[vecino])
esCorte[nodo] = true;
bajo[nodo] = min(bajo[nodo], bajo[vecino]);
} else {
bajo[nodo] = min(bajo[nodo], orden[vecino]);
}
}
if (numHijos[nodo] == 1 && padre[nodo] == 0)
esCorte[nodo] = false;
}
int main() {
int n;
cin >> n;
while (true) {
int x, y;
cin >> x >> y;
if (x == 0 && y == 0) break;
grafo[x].push_back(y);
grafo[y].push_back(x);
}
cin >> inicio >> fin;
dfs(inicio);
for (int i = 1; i <= n; i++) {
if (i == inicio) continue;
if (esCorte[i]) {
cout << i << endl;
return 0;
}
}
cout << "No hay solución" << endl;
return 0;
}
</int></vector></iostream>
P3225 [HNOI2012] Construcción de Minas
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
const int MAXM = 1010;
int n, m;
vector<int> grafo[MAXN];
int orden[MAXN], bajo[MAXN], tiempo;
int pila[MAXN], tope;
int numComponentes;
vector<int> componentes[MAXN];
bool esCorte[MAXN];
int raiz;
void agregarArista(int a, int b) {
grafo[a].push_back(b);
grafo[b].push_back(a);
}
void tarjan(int nodo) {
orden[nodo] = bajo[nodo] = ++tiempo;
pila[++tope] = nodo;
if (nodo == raiz && grafo[nodo].empty()) {
numComponentes++;
componentes[numComponentes].push_back(nodo);
return;
}
int contador = 0;
for (int vecino : grafo[nodo]) {
if (!orden[vecino]) {
tarjan(vecino);
bajo[nodo] = min(bajo[nodo], bajo[vecino]);
if (orden[nodo] <= bajo[vecino]) {
contador++;
if (nodo != raiz || contador > 1) esCorte[nodo] = true;
numComponentes++;
int y;
do {
y = pila[tope--];
componentes[numComponentes].push_back(y);
} while (y != vecino);
componentes[numComponentes].push_back(nodo);
}
} else {
bajo[nodo] = min(bajo[nodo], orden[vecino]);
}
}
}
int main() {
int caso = 1;
while (cin >> m, m) {
for (int i = 1; i <= numComponentes; i++)
componentes[i].clear();
n = tiempo = tope = numComponentes = 0;
fill(grafo.begin(), grafo.begin() + n + 1, vector<int>());
fill(orden, orden + n + 1, 0);
fill(esCorte, esCorte + n + 1, false);
while (m--) {
int a, b;
cin >> a >> b;
n = max(n, a), n = max(n, b);
agregarArista(a, b);
}
for (raiz = 1; raiz <= n; raiz++)
if (!orden[raiz])
tarjan(raiz);
int salidas = 0;
unsigned long long rutas = 1;
for (int i = 1; i <= numComponentes; i++) {
int cortes = 0;
for (int j = 0; j < componentes[i].size(); j++)
if (esCorte[componentes[i][j]])
cortes++;
if (cortes == 0) {
if (componentes[i].size() > 1) {
salidas += 2;
rutas *= componentes[i].size() * (componentes[i].size() - 1) / 2;
} else {
salidas++;
}
} else if (cortes == 1) {
salidas++;
rutas *= componentes[i].size() - 1;
}
}
printf("Caso %d: %d %llu\n", caso++, salidas, rutas);
}
return 0;
}
</int></int></int></algorithm></vector></iostream>
CF51F Caterpillar
El algoritmo de Tarjan también puede aplicarse para resolver problemas de grafos específicos como encontrar caminos en caterpillars. Una caterpillar es un árbol donde al eliminar todos los nodos de grado 1, el resultado es un camino. La implementación utiliza variantes del algoritmo de Tarjan para identificar estructuras específicas en grafos.