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

    Posted on 2019/03/17

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

    制約

    • \(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