fork download 
  1. # Algoritmo para encontrar puentes en un grafo no dirigido usando DFS (Tarjan)
  2. # Un "puente" es una arista cuya eliminación incrementa el número de componentes conexas.
  3.  
  4. # ---------- Entrada y construcción del grafo ----------
  5. n, m = map(int, input("Ingrese n (nodos) y m (aristas): ").split())
  6.  
  7. # Lista de adyacencia (indexada desde 1)
  8. out = [[] for _ in range(n + 1)]
  9.  
  10. for _ in range(m):
  11.     a, b = map(int, input().split())
  12.     out[a].append(b)
  13.     out[b].append(a)  # grafo no dirigido
  14.  
  15. # ---------- Inicialización de estructuras ----------
  16. marked = [False] * (n + 1)  # nodos visitados
  17. depth = [0] * (n + 1)       # profundidad del nodo en el árbol DFS
  18. up = [0] * (n + 1)          # menor profundidad alcanzable desde el subárbol de v
  19.  
  20. # ---------- DFS para detectar puentes ----------
  21. def dfs(v, p):
  22.     marked[v] = True
  23.     up[v] = depth[v]  # al menos puede llegar a sí mismo
  24.  
  25.     for u in out[v]:
  26.         if u == p:
  27.             continue  # no volver por la misma arista
  28.         elif marked[u]:
  29.             # Si u ya fue visitado, es una arista de retroceso
  30.             up[v] = min(up[v], depth[u])
  31.         else:
  32.             # Explorar hijo u
  33.             depth[u] = depth[v] + 1
  34.             dfs(u, v)
  35.             up[v] = min(up[v], up[u])
  36.  
  37.     # Si el valor mínimo alcanzable desde v es mayor
  38.     # que la profundidad de su padre, (p,v) es un puente
  39.     # Esto quiere decir que ninguna backedge llega al nivel del p o a ancestros mas viejos
  40.     if p != -1 and up[v] > depth[p]:
  41.         print(f"{p} -> {v} es un puente")
  42.  
  43. # ---------- Ejecutar DFS (en caso de grafo no conexo, revisar todos los nodos) ----------
  44. for i in range(1, n + 1):
  45.     if not marked[i]:
  46.         depth[i] = 0
  47.         dfs(i, -1) # 
  48.  
Success #stdin #stdout 0.07s 14156KB
comments (?)
stdin 
5 5
1 2
1 3
3 4
3 5
4 5
stdout 
Ingrese n (nodos) y m (aristas): 1 -> 2 es un puente
1 -> 3 es un puente
https://ideone.com/FOyqUX
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!