Cod sursa(job #3375029)

Utilizator TSanSandulescu Toma TSan Data 9 noiembrie 2026 23:17:35
Problema Componente biconexe Scor 80
Compilator py Status done
Runda Arhiva educationala Marime 2.23 kb
import sys
sys.setrecursionlimit(200_000)

infile = open("biconex.in", "r")
outfile = open("biconex.out", "w")

line = infile.readline()
if line:
  nr_noduri, nr_muchii = map(int, line.strip().split())

# Lista de adiacență pentru graful neorientat
adj = {i: [] for i in range(1, nr_noduri + 1)}

for _ in range(nr_muchii):
  u, v = map(int, infile.readline().strip().split())
  adj[u].append(v)
  adj[v].append(u)

# Structuri pentru algoritmul de determinare a componentelor biconexe
tin = [-1] * (nr_noduri + 1)
low = [-1] * (nr_noduri + 1)
timer = 0
stiva = []
biconex_components = []


def dfs(node, p=0):
  global timer
  tin[node] = low[node] = timer
  timer += 1
  children = 0

  for neighbour in adj[node]:
    if neighbour == p:
      continue
    if tin[neighbour] != -1:
      # Muchie de întoarcere (back-edge), actualizăm low
      low[node] = min(low[node], tin[neighbour])
      # Adăugăm muchia în stivă dacă nu a fost vizitată anterior în sens invers
      if tin[neighbour] < tin[node]:
        stiva.append((node, neighbour))
    else:
      # Fiu nevizitat în arborele DFS
      stiva.append((node, neighbour))
      children += 1
      dfs(neighbour, node)
      low[node] = min(low[node], low[neighbour])

      # Condiția de componentă biconexă (sau punct de articulație)
      if low[neighbour] >= tin[node]:
        # Extragem muchiile componentei biconexe din stivă
        component_edges = []
        while True:
          edge = stiva.pop()
          component_edges.append(edge)
          if edge == (node, neighbour):
            break

        # Colectăm nodurile unice din muchiile componentei biconexe
        nodes_in_bcc = set()
        for u_edge, v_edge in component_edges:
          nodes_in_bcc.add(u_edge)
          nodes_in_bcc.add(v_edge)
        biconex_components.append(list(nodes_in_bcc))


# Poate fi apelat din nodul 1 (presupunând graful conex; 
# dacă graful are mai multe componente conexe, se apelează într-o buclă)
for i in range(1, nr_noduri + 1):
  if tin[i] == -1:
    dfs(i)

# Scrierea rezultatelor în fișierul de ieșire biconex.out
outfile.write(str(len(biconex_components)) + "\n")
for bcc in biconex_components:
  outfile.write(" ".join(map(str, bcc)) + "\n")

infile.close()
outfile.close()