ARC 037 B バウムテスト
の続きです。
問題は、与えらたグラフが、木を何個持つか答える問題。
最初に考えた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 問しかできなかったね。残念。