ABC293 D問題 Tying Rope

atcoder.jp

連結成分を調べたいときは 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()