ARC 037 B バウムテスト

qiita.com

の続きです。

問題は、与えらたグラフが、木を何個持つか答える問題。

最初に考えたWAのやつ。単方向。

""" 木である場合は、含まれる頂点を 1 度開始しか通らない """
visited = []
tree = []

def rec(i, mark):
    global visited
    visited[i] = True
    ans = True
    for j in tree[i]:
        if not visited[j]:
            ans &= rec(j)
        else:
            # 木であるものと仮定しているので
            ans &= False
    return ans


def main():
    global visited, tree
    n, m = [int(i) for i in input().split()]
    tree = [[] for i in range(n)]
    for i in range(m):
        u, v = [int(j)-1 for j in input().split()]
        tree[u].append(v)
    visited = [False for i in range(n)]
    ans = 0
    for i in range(n):
        if not visited[i]:
            if rec(i):
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

こいつだと例えば、

6 6
1 3
1 2
2 4
4 5
4 6
5 6

というような入力だと、後の閉路を含むグラフが、すでに探索済み(木とみなしたグラフ)と結合することによって、木の数が減らず、WRになる。

したがって、繋がっているものを一気に探索できればOK。逆方向の辺は、たどる時に消すことに注意する。

""" 最初は辺を双方向(単方向*2)にしておいて、訪れる時に、逆方向を消しておく """
visited = []; table = []


def rec(i):
    global visited, table
    visited[i] = True
    ans = True
    for to, v in enumerate(table[i]):
        # 辺があるか or もう訪れたか
        if v and not visited[to]:
            # 逆方向は消しておく
            table[to][i] = False
            ans &= rec(to)
        # 辺があるのに、行ったことがある
        elif v and visited[to]:
            ans &= False
    return ans


def main():
    global visited, table
    n, m = [int(i) for i in input().split()]
    table = [[False for j in range(n)] for i in range(n)]
    for i in range(m):
        u, v = [int(j)-1 for j in input().split()]
        table[u][v] = True
        table[v][u] = True
    visited = [False for i in range(n)]

    ans = 0
    for i in range(n):
        if not visited[i]:
            if rec(i):
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

今日は 1 問しかできなかったね。残念。