ABC251F - Two Spanning Trees

考え方

入力例として，

3 3
1 2
2 3
3 1

を考えると，DFSで辺を作れば$T_{1}$に，BFSで辺を作れば$T_{2}$になることがわかる．

すでに頂点をつないだかどうかはsetで管理すれば良い．

回答例

スタックを使えばDFSになり，キューを使えばBFSになる．

from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x) - 1, input().split())
    G[u].append(v)
    G[v].append(u)

stack = [(-1, 0)]
used = set()
while stack:
    par, cur = stack.pop()
    if cur in used:continue
    if par != -1:
        print(par + 1, cur + 1)
    used.add(cur)
    for chi in G[cur]:
        if chi not in used:
            stack.append((cur, chi))

q = deque([(-1, 0)])
used = set()
while q:
    par, cur = q.popleft()
    if cur in used:continue
    if par != -1:
        print(par + 1, cur + 1)
    used.add(cur)
    for chi in G[cur]:
        if chi not in used:
            q.append((cur, chi))