PythonでAizu Online Judgeを解く/GRL_3_B - Bridges

Posted on

橋

無向グラフ \(G (V, E)\) の橋を列挙してください（削除すると連結成分が増えるような辺を橋と呼ぶものとします）

URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

制約

  • \(1 \leq |V| \leq 100,000\)
  • \(0 \leq |E| \leq 100,000\)
  • グラフ \(G\) は連結
  • グラフ \(G\) は平行辺を持たない
  • グラフ \(G\) は自己ループを持たない

入力
%python
def input(f):
    global v, e
    global s, t
    
    v, e = map(int, f.readline().split())
    s = [-1 for _ in range(e)]
    t = [-1 for _ in range(e)]
    for i in range(e):
        s[i], t[i] = map(int, f.readline().split())
サンプル入力 #1
%sh
cat <<-EOF > /tmp/input1
4 4
0 1
0 2
1 2
2 3
EOF
%python
with open('/tmp/input1') as f:
    input(f)
    print(v, e)
    print(s)
    print(t)
(4, 4)
[0, 0, 1, 2]
[1, 2, 2, 3]

サンプル入力 #2
%sh
cat <<-EOF > /tmp/input2
5 4
0 1
1 2
2 3
3 4
EOF
(5, 4)
[0, 1, 2, 3]
[1, 2, 3, 4]

考え方


関節点を求めたときと同様に lowlink を利用すると良さそうです 🤔


GRL_3_A:
https://hiroyuki.sano.ninja/notes/78e36032-06f0-42b6-8e56-fc0a08ca05a2


実装
%python
import sys
sys.setrecursionlimit(1000000)

def solve():
    g = [[] for _ in range(v)]
    for i in range(e):
        g[s[i]].append(t[i])
        g[t[i]].append(s[i])
    
    used = [False for _ in range(v)]
    ord = [-1 for _ in range(v)]
    low = [10**6 for _ in range(v)]
    res = []
    
    def rec(cur, prev, d):
        if used[cur]:
            return
        used[cur] = True
        ord[cur] = d
        low[cur] = ord[cur]
        
        cnt = 0
        for nxt in g[cur]:
            if not used[nxt]:
                cnt += 1
                rec(nxt, cur, d+1)
                low[cur] = min(low[cur], low[nxt])
                if prev >= 0 and ord[cur] < low[nxt]:
                    res.append((min(cur, nxt), max(cur, nxt)))
            elif nxt != prev:
                low[cur] = min(low[cur], ord[nxt])
        
        if prev == -1 and (cnt >= 2 or len(g[cur]) == 1):
            for nxt in g[cur]:
                res.append((min(cur, nxt), max(cur, nxt)))
    
    rec(0, -1, 0)
    
    for src, dst in sorted(res):
        print('{} {}'.format(src, dst))
サンプル
%python
with open('/tmp/input1') as f:
    input(f)
    solve()
2 3

%python
with open('/tmp/input2') as f:
    input(f)
    solve()
0 1
1 2
2 3
3 4

Wrong Answer #1: 根は cnt >= 2 or 元グラフの次数が 1
%sh
curl -s https://judgedat.u-aizu.ac.jp/testcases/GRL_3_B/4/in > /tmp/in4.txt
head /tmp/in4.txt
3 2
0 1
0 2

%python
with open('/tmp/in4.txt') as f:
    input(f)
    solve()
0 1
0 2

Wrong Answer #2: 関節点を持つ辺が必ずしも橋にはならない
%sh
curl -s https://judgedat.u-aizu.ac.jp/testcases/GRL_3_B/8/in > /tmp/in8.txt
head /tmp/in8.txt
5 5
0 1
1 2
1 3
2 3
3 4

%python
with open('/tmp/in8.txt') as f:
    input(f)
    solve()
0 1
3 4



辺 (1, 2) が橋ではありませんでした


-                if prev >= 0 and ord[cur] <= low[nxt]:
+                if prev >= 0 and ord[cur] < low[nxt]:
                     res.append((cur, nxt))



%python
with open('/tmp/in8.txt') as f:
    input(f)
    solve()
0 1
3 4

Wrong Answer #3: 出力は各レコードも昇順
%sh
curl -s https://judgedat.u-aizu.ac.jp/testcases/GRL_3_B/11/in > /tmp/in11.txt
head /tmp/in11.txt
16 19
0 1
0 3
0 2
1 3
2 3
3 6
4 6
5 6
6 7

%python
with open('/tmp/in11.txt') as f:
    input(f)

print('''
%html
<div id="stage11"></div>
<script>
(function() {
function visualize1() {
    const graph = new Graph(d3.select('#stage11'));
''')

for i in range(v):
    print('graph.addNode("{}");'.format(i))
for i in range(e):
    print('graph.addEdge("{}", "{}");'.format(s[i], t[i]))

print('''
    graph.update();
    setTimeout(function() {
        graph.simulation.stop();
    }, 3000);
}

const wait1 = setTimeout(visualize1, 2000);
window.d3MinJS.addEventListener('load', function() {
    clearTimeout(wait1);
    visualize1();
});
})();
</script>
''')
%python
with open('/tmp/in11.txt') as f:
    input(f)
    solve()
3 6
4 6
5 6
6 7
6 9
9 12
10 11



(6, 4) を (4, 6) にする必要があります


Wrong Answer #4: 並べ替えたあとのリストを並べ替える
%sh
curl -s https://judgedat.u-aizu.ac.jp/testcases/GRL_3_B/20/in > /tmp/in20.txt
head /tmp/in20.txt
9 10
0 1
0 2
1 4
2 5
3 4
3 6
4 5
4 7
5 7

%python
with open('/tmp/in20.txt') as f:
    input(f)
    solve()
3 4
3 6
7 8



1行目と2行目が逆になっています


アニメーション
%python