D - Decayed Bridges

はじめに

競技プログラミングAtCoder Beginner Contest 120
D - Decayed Bridges
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

N個の島と M本の橋があります。
i番目の橋は Ai番目の島と Bi番目の島を繋いでおり、双方向に行き来可能です。
はじめ、どの2つの島についてもいくつかの橋を渡って互いに行き来できます。
調査の結果、老朽化のためこれら M本の橋は 1番目の橋から順に全て崩落することがわかりました。
「いくつかの橋を渡って互いに行き来できなくなった 2つの島の組 (a,b)(a<b) の数」を不便さと呼ぶことにします。
各i(1≤i≤M)について、i番目の橋が崩落した直後の不便さを求めてください。

制約

・入力は全て整数である。
・2≤N≤10^5
・1≤M≤10^5
・1≤Ai<Bi≤N
・(Ai,Bi)の組は全て異なる。
・初期状態における不便さは0である。

入力

入力は以下の形式で標準入力から与えられる。

N M
A1 B1
A2 B2
⋮
AM BM

出力

i=1,2,...,Mの順に、i番目の橋が崩落した直後の不便さを出力せよ。
答えが32bit整数型に収まらない場合があることに注意すること。

解き方

以下を参考にしています。
https://img.atcoder.jp/abc120/editorial.pdf
atcoder.jp

考える順序

最終的な出力は
全ての橋がある状態から
一つずつ橋が崩壊する順序に「不便さ」を
出していきますが
橋がある状態から一つずつ橋がなくなっていき
「不便さ」が増えていく状態を考えるよりも
橋がない状態から一つずつ橋が増えていき
「不便さ」が解消されていく状態を考える方が楽なので
最終的な出力とは逆に考えていきます。

後入れ先出しのStackに保存しておけば、
何もしなくてもStackに保存した順序と逆の順序で
出力してくれます。

橋が増えていく(不便さが減っていく)状態を考える

一番初めにすべての橋がない状態の「不便さ」は
以下のように出せます。

(N * (N - 1)) / 2

橋が一つもなくどの島にも行き来できない状態なので
橋の組み合わせの数がそのまま「不便さ」になります。

次に橋が増えていくときの「不便さ」について考えてみます。
これには2つのパターンが考えられます。
①行き来することが出来なかった島に橋がかかる
②もともと行き来することが出来た島に橋がかかる


①行き来することが出来なかった島に橋がかかる
例えば、島1,2,3,4が存在し
既に1,2には橋が架かっているとします。
ここにさらに、2と3の間に橋がかかった場合は
(1,3)(2,3)という行き来が出来なかった島の組み合わせが
新たに行き来できるようになるため
このパターンが当てはまります。

このとき「不便さ」は以下のようになります。
一つ前の「不便さ」をH、(Stackに入っている最新の値(Stack.Peek()))
橋が架かるグループのそれぞれの要素の数
上の島1,2,3,4の例でいうと、
既に橋が架かっている「1,2」とかかっていない「3」の要素の数
すなわち「2」と「1」)をA,Bとおくと

H-A*B

となります。


②もともと行き来することが出来た島に橋がかかる
例えば、島1,2,3,4が存在し
既に1,2,3には「1-2-3」と橋が架かっているとします。
このとき行き来できる島は
(1,2)(1,3)(2,3)です。
ここにさらに、1と3の間に橋がかかった場合は

1 ─ 2
│/
3

となり
もともと行き来できた島に橋がかかるだけで
新たに行き来できる島は増えないので
このパターンが当てはまります。

このとき「不便さ」は以下のようになります。
一つ前の「不便さ」をH、(Stackに入っている最新の値(Stack.Peek()))とおくと
新たに行き来できる島は増減せず
「不便さ」に変化はないので

H

となります。

「不便さ」の変化は①と②の2パターンしかないので
橋が架かるグループのそれぞれの要素の数A,Bが求められれば
「不便さ」を出していくことができます。

しかし、
単純に橋が架かるグループのそれぞれの要素の数A,Bを求めると タイムアウトしてしまうので
効率的に求めることが必要になります。

橋が架かるグループのそれぞれの要素の数を求める

Union-Findと呼ばれるデータ構造を用いると
橋が架かるグループのそれぞれの要素の数A,Bを
効率的に求めることができます。

Union find(素集合データ構造)
Union-Find木の解説と例題 - Qiita

Union-Findの本来の形は
root : 枝の根(親)を返す関数
unite : 根(親)が同じ出ない二つの枝を併合する関数
same : 二つの枝が同じ根に属するかどうかを返す関数
などがありますが以下の解答ではこの形にしていません。

parentという配列とsizeという配列を用いて解いています。
parent[] : 枝の親を格納しておく配列
これが同じなら同じ親に属しているということになります。
島1,2,3,4があり、現在の橋の状態が

1 ─ 2 4
│/
3

とするとparentには以下のように値が入っています。
配列番号に合わせているので、島の数とは-1ずれています。
また、親の数は常に繋がっている要素の中で一番小さいものとしています。

parent[0]=0(1の島の親は自分自身なので自分が入る)
parent[1]=0(2の島の親は1なので0が入る)
parent[2]=0(3の島の親は1なので0が入る)
parent[3]=3(4の島の親は自分自身なので自分が入る)

size[] : 枝の要素数を格納しておく配列
島1,2,3,4があり、現在の橋の状態が

1 ─ 2 4
│/
3

とするとsizeには以下のように値が入っています。
配列番号に合わせているので、島の数とは-1ずれています。
また、親の数は常に繋がっている要素の中で一番小さいものとしています。

parent[0]=3(1の島の親は自分自身で、2と3が枝としてぶら下がっているので要素数は3)
parent[1]=1(2の島の親は1で、自分には何もぶら下がっていないので要素数は1)
parent[2]=1(3の島の親は1で、自分には何もぶら下がっていないので要素数は1)
parent[3]=1(4の島の親は自分自身で、自分には何もぶら下がっていないので要素数は1)

(この問題では、親の要素数のみを見て
判断していけばよい、
かつ
一度枝になってしまった島が親になることはないので
親以外のサイズは更新しなくても大丈夫そうでした。)

橋が架かる島の親をparent配列から取り出し、
親のもつ要素数をsize配列から取り出せば
「橋が架かるグループのそれぞれの要素の数」
が分かり、
問題を解くことができます。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Dmondai
{
    static int[] parent;
    static void Main()
    {
        var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        //島の数
        var N = nm[0];
        //橋の数
        var M = nm[1];

        //入力されるAi番目の島とBi番目の島を保存するリスト
        var AB = new List<int[]>();
        for (int i = 0; i < M; ++i)
        {
            var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
            AB.Add(new int[2] { ab[0] - 1, ab[1] - 1 });
        }

        //Union-Find

        //枝の要素数を格納しておく配列
        var size = new long[N];
        //枝の親を格納しておく配列
        parent = new int[N];

        //size[]とparent[]を初期化
        for (int i = 0; i < N; ++i)
        {
            //全ての島にぶら下がる枝は、自分の島だけ
            size[i] = 1;
            //全ての島が自分が親
            parent[i] = i;
        }
        
        //答えを格納するStack
        var ans = new Stack<long>();
        //橋が一つもかかっていない状態を格納
        ans.Push(((long)N * ((long)N - 1)) / 2);

        //橋が増えたときの「不便さ」の変化
        for (int i = M - 1; 0 < i; --i)
        {
            //橋がかかるそれぞれの島の親を取得
            var ab = AB[i];
            var parent1 = GetParent(ab[0]);
            var parent2 = GetParent(ab[1]);
            //もし親が異なるならば
            if (parent1 != parent2)
            {
                //「不便さ」が減る
                ans.Push(ans.Peek() - (size[parent1] * size[parent2]));
                //親を片方の親に統一
                //以下の場合(parent2)の島の親が(parent1)になり、(parent2)は(parent1)にぶら下がる枝になる
                parent[parent2] = parent1;
                //親のサイズを更新
                //(parent1)が(parent2)を吸収して大きくなったので(parent2)のサイズを足す
                size[parent1] += size[parent2];
            }
            //親が同じなら「不便さ」に変化はないので直近の値を入れる
            else ans.Push(ans.Peek());
        }
        //Stackに入れたのでそのまま出力すれば問題なし
        for (int i = 0; i < M; ++i) Console.WriteLine(ans.Pop());
    }

    //親を返す関数
    //ここで枝の親が変化していた場合、枝に更新がかかる
    //例えば 1 2-3 という繋がりがmain関数の中で 1-2-3 へと変化したとすると
    //main関数内で2の親は1であることが更新されるが、
    //3の親は2の親のままになっているので、ここで正しい情報に更新する
    static int GetParent(int num)
    {
        //配列の番号と親の番号が一致していれば親
        if (parent[num] == num) return num;
        //一致していなければ、親ではないので上にさかのぼる
        else return parent[num] = GetParent(parent[num]);
    }
}