Pagini recente » Cod sursa (job #491944) | Cod sursa (job #482385) | Cod sursa (job #1594802) | Cod sursa (job #3255753) | Cod sursa (job #2795827)
import sys
sys.setrecursionlimit(10 ** 6)
def biconex(file, file2):
import collections
f = open(file, "r")
g = open(file2, "w")
n, m = [int(n) for n in f.readline().split()]
d = [[] for _ in range(n + 1)]
for i in range(m):
n1, n2 = [int(n) for n in f.readline().split()]
d[n1].append(n2)
d[n2].append(n1)
ids = (n+1)*[0]
lowlink = (n+1)*[0]
parent = (n+1)*[0]
biconex = []
stack = collections.deque()
nid = collections.deque()
def DFS(n):
nid.append(0)
ids[n] = len(nid)
lowlink[n] = len(nid)
for i in d[n]:
if ids[i] == 0:
haschild = True
parent[i] = n
stack.append((n, i))
DFS(i)
lowlink[n] = min(lowlink[n], lowlink[i])
if (parent[n] == 0 and haschild) or (parent[n] != 0 and lowlink[i] >= ids[n]):
k = stack.pop()
c = {k[0]}
while k != (n, i):
k = stack.pop()
c.add(k[0])
if len(c) > 1:
biconex.append(sorted(c))
else:
c.add(k[1])
biconex.append(sorted(c))
elif parent[n] != i and lowlink[n] > ids[i]:
lowlink[n] = ids[i]
stack.append((n, i))
for i in range(1, n + 1):
if ids[i] == 0:
DFS(i)
g.write(str(len(biconex)))
for c in biconex:
g.write('\n'+" ".join(str(n) for n in c))
f.close()
g.close()
biconex("biconex.in", "biconex.out")