連結成分を調べたいときは Union-Find 木
Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。
同じグループに属する頂点を木構造で表現することにして、頂点 x の親を parent[x] に記録していきます。
頂点番号と親の番号が同じ頂点は、グループの代表(root) になります。
最初すべての頂点について parent[i] = i で初期化して、辺で結ばれたグループを1つのグループにまとめる処理を行っていきます。
また、各頂点に属する辺の数を記録するための配列を用意して、辺を追加するたびに、その一方の頂点で数を1つずつ増やしていきます。
(二重カウントを避けるために、一方の頂点だけで数えていきます)
最後に、各頂点の root を求め、その root に頂点の数と辺の数を加算していき、頂点の数と辺の数が一致するかどうか調べます。
コード例 (Julia)
function solve() # 入力 readInts() = parse.(Int,split(readline())) readInt() = parse(Int,readline()) N,M = readInts() parent = Vector{Int}(1:N) # Union-Find tree : 親ノード番号 n_edge = zeros(N) # 辺の数のカウント用 # 関数定義 root(x) = (parent[x]==x ? x : parent[x] = root(parent[x])) unite(x,y) = ( root(x)!=root(y) ? ( parent[root(x)] = root(y) ) : root(x) ) # 辺を追加していく for i = 1:M u,v = readInts() unite(u,v) # Union-Find tree でグループ結合 n_edge[u] += 1 # 辺の数のカウント end n_node = zeros(N) # 頂点の数のカウント用 for i = 1:N r = root(i) n_node[r] += 1 # root に属する頂点のカウント if r != i n_edge[r] += n_edge[i] # root に属する辺のカウント end end for i = 1:N if n_node[i] > 0 # i を root とするグループで頂点数と辺数が一致するか調べる if n_node[i] != n_edge[i] println("No") return end end end println("Yes") return end # function solve # main solve()
