fork download 
  1. # Algoritmo de Tarjan para encontrar PUNTOS DE ARTICULACIÓN en un grafo no dirigido.
  2. # Un "punto de articulación" es un vértice cuya eliminación incrementa
  3. # el número de componentes conexas del grafo.
  4.  
  5. # ---------- Entrada y construcción del grafo ----------
  6. n, m = map(int, input("Ingrese n (nodos) y m (aristas): ").split())
  7.  
  8. # Lista de adyacencia (indexada desde 1)
  9. out = [[] for _ in range(n + 1)]
  10.  
  11. for _ in range(m):
  12.     a, b = map(int, input().split())
  13.     out[a].append(b)
  14.     out[b].append(a)  # grafo no dirigido
  15.  
  16. # ---------- Inicialización de estructuras ----------
  17. marked = [False] * (n + 1)  # nodos visitados
  18. depth = [0] * (n + 1)       # profundidad del nodo en el árbol DFS
  19. up = [0] * (n + 1)          # menor profundidad alcanzable desde el subárbol
  20.  
  21. # ---------- DFS para detectar puntos de articulación ----------
  22. def dfs(v, p):
  23.     marked[v] = True
  24.     up[v] = depth[v]
  25.     children = 0  # cantidad de hijos directos en el árbol DFS
  26.  
  27.     for u in out[v]:
  28.         if u == p:
  29.             continue
  30.         elif marked[u]:
  31.             # Back edge
  32.             up[v] = min(up[v], depth[u])
  33.         else:
  34.             # Arista de árbol
  35.             depth[u] = depth[v] + 1
  36.             dfs(u, v)
  37.             up[v] = min(up[v], up[u])
  38.  
  39.             # Si el subárbol de u no puede alcanzar un ancestro de v,
  40.             # entonces v es un punto de articulación
  41.             if up[u] >= depth[v] and p != -1:
  42. 	            print(v, "es punto de articulacion")
  43.  
  44.             children += 1
  45.  
  46.     # Caso especial: si v es raíz del DFS y tiene más de un hijo, es articulación
  47.     if p == -1 and children > 1:
  48.         print(v, "es punto de articulacion")
  49.  
  50.  
  51. # ---------- Ejecutar DFS (en caso de grafo no conexo) ----------
  52. for i in range(1, n + 1):
  53.     if not marked[i]:
  54.         depth[i] = 0
  55.         dfs(i, -1)
  56.  
Success #stdin #stdout 0.1s 14168KB
comments (?)
stdin 
5 5
1 2
1 3
3 4
3 5
4 5
stdout 
Ingrese n (nodos) y m (aristas): 3 es punto de articulacion
1 es punto de articulacion
https://ideone.com/4sx3W9
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!