連結成分を調べたいときは Union-Find 木
Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。
ロープを頂点とみなして、同じグループに属する頂点を木構造で表現することを考えます。Union-Find 木の表現として、頂点 x の親を parent[x] に記録していきます。
頂点番号と親の番号が同じ頂点は、グループの代表(root) になります。
最初すべての頂点について parent[i] = i で初期化して、辺で結ばれたグループを1つのグループにまとめる処理を行っていきます。
各ロープにつなげることができるのは両端に1回ずつだけなので、頂点の次数は 2以下で枝別れのない形状になります。環状になる場合、各頂点の次数はすべて2になります。環状にならない場合、2つの頂点の次数が1で、それ以外の次数が2になると考えられます。
ここで、1本のロープの両端を結ぶケースがあり、この場合1本のロープだけで環状になることに注意する必要があります。
コード例 (Julia)
function solve() # 入力 readInts() = parse.(Int,split(readline())) readInt() = parse(Int,readline()) N,M = readInts() parent = Vector{Int}(1:N) # Union-Find tree : 親ノード番号 order = 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 A,B,C,D = split(readline()) p = parse(Int,A) q = parse(Int,C) unite(p,q) order[p] += 1 order[q] += 1 end order1 = zeros(N) # 次数 1 の頂点数 nv = zeros(N) # グループの頂点数 for i = 1:N r = root(i) nv[r] += 1 # root が r のグループに属する頂点の数 if order[i] == 1 order1[r] += 1 # グループに属する次数 1 の頂点の数 end end X = 0 Y = 0 for i = 1:N if nv[i] == 1 # 1 本ロープのみ if order[i] > 0 X += 1 # 1 本のロープの両端が結ばれて環状になる場合 else Y += 1 # 1 本のロープのみで結ばれていない場合 end elseif nv[i] > 1 if order1[i] == 2 Y += 1 # 片側のみが結ばれたロープが 2 本ある場合 else X += 1 # すべてのロープが両端結ばれている場合 end end end println(X," ",Y) end # function solve # main solve()