AtCoder NoviStepsを埋めてみる(15) Union-Find 1Q

AtCoder NoviStepsを埋めてみる(14) Union-Findで二部グラフ判定の続きです。今回は Union-Find の応用問題です。

Contents

1 C – チームの旗の色
2 E – Reachability Query
3 D – Decayed Bridges
4 K - 連結チェック
5 E – K-th Largest Connected Components
6 E – Good Graph
7 E – Round Trip
8 Blackout 2
9 E – Graph Destruction
10 E – Just one
11 Sum of Maximum Weights
12 E – 1 or 2

C – チームの旗の色

問題の概要

N 人の選手が所属するスポーツクラブがある。最初、各選手はそれぞれ 1 人だけからなる別々のチームに所属している。
各チームは旗の色を 1 つ持つことができるが、初期状態ではどのチームにも旗の色は設定されていない。
「U[i] が所属するチームと選手 V[i] が所属するチームを合併して 1 つのチームにするとともに合併後のチームの旗の色を C[i] に設定する」という操作を M 回繰り返す。
M 回の操作が終わった後のチームの旗の色の種類数を求めよ。

チームの旗の色をどう管理するかが問題です。

まず、N 個の頂点をつくります。これがひとりひとりの選手となります。それと同時に長さ N の int 型配列を用意し、初期値を 0 とします。これはそれぞれの選手が属するチームの色です。

チームを合併する動作は merge すればよいです。そして merge したらその連結成分の代表元を求めて、これに色を設定します。チームの選手全員に色を設定するのは時間がかかるので代表選手にだけ色を設定するのです。

操作が終わったら各チームの代表者がもつ色を調べてその種類数を求めます。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nm[0];
        int M = nm[1];

        Dsu dsu = new Dsu(N);
        int[] colors = new int[N];

        for (int i = 0; i < M; i++)
        {
            int[] uvc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = uvc[0] - 1;
            int v = uvc[1] - 1;
            int c = uvc[2];
            dsu.Merge(u, v);
            int leader = dsu.Leader(u);
            colors[leader] = c;
        }

        HashSet<int> set = new HashSet<int>();
        foreach (var group in dsu.Groups())
        {
            int leader = dsu.Leader(group[0]);
            if (colors[leader] != 0)
                set.Add(colors[leader]);
        }
        Console.WriteLine(set.Count);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

Dsu dsu = new Dsu(N);

int[] colors = new int[N];

for (int i = 0; i < M; i++)

{

int[] uvc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uvc[0] - 1;

int v = uvc[1] - 1;

int c = uvc[2];

dsu.Merge(u, v);

int leader = dsu.Leader(u);

colors[leader] = c;

}

HashSet<int> set = new HashSet<int>();

foreach (var group in dsu.Groups())

{

int leader = dsu.Leader(group[0]);

if (colors[leader] != 0)

set.Add(colors[leader]);

}

Console.WriteLine(set.Count);

}

E – Reachability Query

問題の概要

N 頂点 0 辺の無向グラフが与えられる。
最初はすべての頂点が白色である。
3 種類のクエリが全部で Q 個あるので処理せよ。
タイプ 1 : 頂点 u, v を結ぶ無向辺を追加する。
タイプ 2 : 頂点 v が白色なら黒色に、黒色なら白色に変更する。
タイプ 3 : 頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるか判定する。

タイプ 1 の「頂点 u, v を結ぶ無向辺を追加する」という処理は頂点を merge すればよいです。またタイプ 3 の「頂点 v から 0 本以上の辺を辿って黒色の頂点に到達できるか判定する」は、頂点 v が属する連結成分内に黒い頂点がひとつでもあれば判定結果は “Yes” となります。

連結成分内にある黒い頂点の個数を管理するために代表元に個数の情報をもたせます。「頂点 u, v を結ぶ無向辺を追加する」という処理は頂点を merge するだけでなく、代表元がもつ黒頂点の個数も合算します。このときすでに同一連結成分内にある頂点同士を merge しようとするとおかしなことになるので、この処理はふたつの頂点が同一連結成分内にない場合だけおこなうようにします。

タイプ 2 の「頂点v が白色なら黒色に、黒色なら白色に変更する」という処理は、頂点 v が属する連結成分の代表元がもつ黒頂点の個数を増減させるようにします。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nq[0];
        int Q = nq[1];

        Dsu dsu = new Dsu(N);

        int[] counts = new int[N];
        bool[] isblacks = new bool[N];

        List<string> ans = new List<string>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            if (t == 1)
            {
                int u = query[1] - 1;
                int v = query[2] - 1;

                // この処理は u, v がすでに同一連結成分内にあるときは実行してはならない
                if (!dsu.Same(u, v))
                {
                    // merge するだけでなく 各連結成分がもつ黒頂点の個数も合算する
                    int lu = dsu.Leader(u);
                    int lv = dsu.Leader(v);
                    int cnt = counts[lu] + counts[lv];
                    int leader = dsu.Merge(u, v);
                    counts[leader] = cnt;
                }
            }
            if (t == 2)
            {
                int v = query[1] - 1;
                isblacks[v] = !isblacks[v];
                int leader = dsu.Leader(v);
                if (isblacks[v])
                    counts[leader]++;
                else
                    counts[leader]--;
            }
            if (t == 3)
            {
                int v = query[1] - 1;
                int leader = dsu.Leader(v);
                ans.Add(counts[leader] > 0 ? "Yes" : "No");
            }
        }

        foreach (var s in ans)
            Console.WriteLine(s);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nq[0];

int Q = nq[1];

Dsu dsu = new Dsu(N);

int[] counts = new int[N];

bool[] isblacks = new bool[N];

List<string> ans = new List<string>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

int u = query[1] - 1;

int v = query[2] - 1;

// この処理は u, v がすでに同一連結成分内にあるときは実行してはならない

if (!dsu.Same(u, v))

{

// merge するだけでなく各連結成分がもつ黒頂点の個数も合算する

int lu = dsu.Leader(u);

int lv = dsu.Leader(v);

int cnt = counts[lu] + counts[lv];

int leader = dsu.Merge(u, v);

counts[leader] = cnt;

}

if (t == 2)

{

int v = query[1] - 1;

isblacks[v] = !isblacks[v];

int leader = dsu.Leader(v);

if (isblacks[v])

counts[leader]++;

else

counts[leader]--;

}

if (t == 3)

{

int v = query[1] - 1;

int leader = dsu.Leader(v);

ans.Add(counts[leader] > 0 ? "Yes" : "No");

}

foreach (var s in ans)

Console.WriteLine(s);

}

D – Decayed Bridges

問題の概要

N 個の島と M 本の橋がある。i 番目の橋は A[i] 番目の島と B[i] 番目の島を繋いでいる。
M 本の橋を 1 番目の橋から順に取り除いていく。これによって互いに行き来できなくなった 2 つの島の組 (a, b)の数を不便さと定義する。
各 i について i 番目の橋を取り除いた直後の不便さを求めよ。

Union-Find では merge の処理はできますが、分割の処理はできません。そこで時間の流れを逆にして橋がひとつもない状態から橋を追加していく処理を考えます。

ぞれぞれの頂点から行き来可能な島の組は連結成分の大きさを size とすると size * (size – 1) / 2 で計算できます。merge する前はふたつの頂点はそれぞれ異なる連結成分内に存在するのでそれぞれの和を考えます。merge したあとはひとつの連結成分になるのでもう一度連結成分の大きさを取得して size * (size – 1) / 2 を計算します。この差が不便さの変動量となります。

橋がひとつもない最初の状態における不便さは N (N – 1) / 2 であり、最終的な不便さは 0 となります。不便さの差分から各段階における不便さを計算してこれを記録しておけば、これを逆順で出力することで解が得られます。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nm[0];
        int M = nm[1];

        List<(int, int)> E = new List<(int, int)>();
        for (int i = 0; i < M; i++)
        {
            int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = ab[0] - 1;
            int b = ab[1] - 1;
            E.Add((a, b));
        }
        E.Reverse();

        long value = 1L * N * (N - 1) / 2;
        List<long> ans = new List<long>();

        Dsu dsu = new Dsu(N);
        foreach (var edge in E)
        {
            ans.Add(value);

            if (!dsu.Same(edge.Item1, edge.Item2))
            {
                long size1 = dsu.Size(edge.Item1);
                long size2 = dsu.Size(edge.Item2);
                long before = size1 * (size1 - 1) / 2 + size2 * (size2 - 1) / 2;

                dsu.Merge(edge.Item1, edge.Item2);

                long size = dsu.Size(edge.Item1);
                long after = size * (size - 1) / 2;
                value -= after - before;
            }
        }

        ans.Reverse();
        foreach (var v in ans)
            Console.WriteLine(v);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

List<(int, int)> E = new List<(int, int)>();

for (int i = 0; i < M; i++)

{

int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int a = ab[0] - 1;

int b = ab[1] - 1;

E.Add((a, b));

}

E.Reverse();

long value = 1L * N * (N - 1) / 2;

List<long> ans = new List<long>();

Dsu dsu = new Dsu(N);

foreach (var edge in E)

{

ans.Add(value);

if (!dsu.Same(edge.Item1, edge.Item2))

{

long size1 = dsu.Size(edge.Item1);

long size2 = dsu.Size(edge.Item2);

long before = size1 * (size1 - 1) / 2 + size2 * (size2 - 1) / 2;

dsu.Merge(edge.Item1, edge.Item2);

long size = dsu.Size(edge.Item1);

long after = size * (size - 1) / 2;

value -= after - before;

}

ans.Reverse();

foreach (var v in ans)

Console.WriteLine(v);

}

E – K-th Largest Connected Components

問題の概要

N 頂点 0 辺の無向グラフがある。
Q 個のクエリが与えられるので処理せよ。
タイプ 1 : 頂点 u と頂点 v の間に辺を追加する。
タイプ 2 : 頂点 v と連結な頂点の中で、k 番目に頂点番号が大きいものを出力する。ただし、頂点 v と連結な頂点が k 個未満のときは -1 を出力する（ただし k ≦ 10）。

連結な頂点を格納するリストの配列を定義します。そして連結成分に属する頂点は代表元で管理します。「頂点 u と頂点 v の間に辺を追加する」処理はそれぞれの頂点が属する連結成分の頂点を merge すればよいです。k ≦ 10 なので頂点番号が大きいもの 10 個だけあれば充分です。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nq[0];
        int Q = nq[1];

        Dsu dsu = new Dsu(N);
        List<int>[] vList = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            vList[i] = new List<int>();
            vList[i].Add(i);
        }

        List<int> ans = new List<int>();
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            if (t == 1)
            {
                int u = query[1] - 1;
                int v = query[2] - 1;
                if (!dsu.Same(u, v))
                {
                    int lu = dsu.Leader(u);
                    int lv = dsu.Leader(v);
                    List<int> list = new List<int>(vList[lu]);
                    list.AddRange(vList[lv]);
                    list = list.OrderByDescending(_ => _).Take(10).ToList();
                    int leader = dsu.Merge(u, v);
                    vList[leader] = list;
                }
            }
            if (t == 2)
            {
                int v = query[1] - 1;
                int k = query[2];
                int leader = dsu.Leader(v);
                ans.Add(vList[leader].Count >= k ? vList[leader][k - 1] + 1 : -1);
            }
        }
        foreach (int v in ans)
            Console.WriteLine(v);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nq[0];

int Q = nq[1];

Dsu dsu = new Dsu(N);

List<int>[] vList = new List<int>[N];

for (int i = 0; i < N; i++)

{

vList[i] = new List<int>();

vList[i].Add(i);

}

List<int> ans = new List<int>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

int u = query[1] - 1;

int v = query[2] - 1;

if (!dsu.Same(u, v))

{

int lu = dsu.Leader(u);

int lv = dsu.Leader(v);

List<int> list = new List<int>(vList[lu]);

list.AddRange(vList[lv]);

list = list.OrderByDescending(_ => _).Take(10).ToList();

int leader = dsu.Merge(u, v);

vList[leader] = list;

}

if (t == 2)

{

int v = query[1] - 1;

int k = query[2];

int leader = dsu.Leader(v);

ans.Add(vList[leader].Count >= k ? vList[leader][k - 1] + 1 : -1);

}

foreach (int v in ans)

Console.WriteLine(v);

}

E – Good Graph

問題の概要

N 頂点 M 辺の無向グラフが与えられる。
すべての i = 1, 2, …, K について頂点 x[i] と頂点 y[i] を結ぶパスが存在しないなら、良いグラフと呼ぶことにする。
与えられるグラフ G は良いグラフである。
Q 個の独立な質問に答えよ。
（i 番目の質問）入力で与えられたグラフの頂点 p[i] と頂点 q[i] を結ぶ無向辺を追加して得られるグラフは良いグラフか？

無向辺を追加することでどのふたつの連結成分が merge されてはいけないかを考えます。連結成分の代表元をみればわかります。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nm[0];
        int M = nm[1];

        Dsu dsu = new Dsu(N);
        for (int i = 0; i < M; i++)
        {
            int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = uv[0] - 1;
            int v = uv[1] - 1;
            dsu.Merge(u, v);
        }

        // 連結させてはいけない連結成分のペアがわかるようにする
        // 実際に格納されるのは連結成分の代表元をカンマ区切りした文字列
        HashSet<string> pair_set = new HashSet<string>();

        int K = int.Parse(Console.ReadLine());
        for (int i = 0; i < K; i++)
        {
            int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int x = xy[0] - 1;
            int y = xy[1] - 1;
            int lx = dsu.Leader(x);
            int ly = dsu.Leader(y);
            pair_set.Add($"{lx},{ly}");
            pair_set.Add($"{ly},{lx}");
        }

        List<string> ans = new List<string>();

        int Q = int.Parse(Console.ReadLine());
        for (int i = 0; i < Q; i++)
        {
            int[] pq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int p = pq[0] - 1;
            int q = pq[1] - 1;

            // 連結させてはいけない連結成分のペアでないなら "Yes"
            int lp = dsu.Leader(p);
            int lq = dsu.Leader(q);
            ans.Add(pair_set.Contains($"{lp},{lq}") ? "No" : "Yes");
        }
        foreach (var s in ans)
            Console.WriteLine(s);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

Dsu dsu = new Dsu(N);

for (int i = 0; i < M; i++)

{

int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uv[0] - 1;

int v = uv[1] - 1;

dsu.Merge(u, v);

}

// 連結させてはいけない連結成分のペアがわかるようにする

// 実際に格納されるのは連結成分の代表元をカンマ区切りした文字列

HashSet<string> pair_set = new HashSet<string>();

int K = int.Parse(Console.ReadLine());

for (int i = 0; i < K; i++)

{

int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int x = xy[0] - 1;

int y = xy[1] - 1;

int lx = dsu.Leader(x);

int ly = dsu.Leader(y);

pair_set.Add($"{lx},{ly}");

pair_set.Add($"{ly},{lx}");

}

List<string> ans = new List<string>();

int Q = int.Parse(Console.ReadLine());

for (int i = 0; i < Q; i++)

{

int[] pq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int p = pq[0] - 1;

int q = pq[1] - 1;

// 連結させてはいけない連結成分のペアでないなら "Yes"

int lp = dsu.Leader(p);

int lq = dsu.Leader(q);

ans.Add(pair_set.Contains($"{lp},{lq}") ? "No" : "Yes");

}

foreach (var s in ans)

Console.WriteLine(s);

}

E – Round Trip

問題の概要

縦 H 行、横 W 列のグリッドがある。
各マスには ‘S’, ‘,’, ‘#’ のいずれかの文字が書かれていて、それぞれ始点、道、障害物を表している。
始点のマスを出発し、上下または左右に隣接するマスに移動することを繰り返して、障害物のマスを通らずに始点のマスへ戻ってくるような長さ 4 以上の経路であって、最初と最後を除き同じマスを通らないようなものが存在するか判定せよ。

隣り合う ‘.’ 同士を merge します。始点の上下左右のマスのペアのうち同じ連結成分に属するものがあれば “Yes”、ないなら “No” です。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hw[0];
        int W = hw[1];

        char[][] grid = new char[H][];
        for (int r = 0; r < H; r++)
            grid[r] = Console.ReadLine().ToArray();

        int ToIndex(int r, int c) => r * W + c;

        Dsu dsu = new Dsu(H * W);
        int sr = 0;
        int sc = 0;
        for (int r = 0; r < H; r++)
        {
            for (int c = 0; c < W; c++)
            {
                int idx = ToIndex(r, c);
                if (grid[r][c] == '.')
                {
                    if (r - 1 >= 0 && grid[r - 1][c] == '.')
                        dsu.Merge(idx, ToIndex(r - 1, c));
                    if (r + 1 < H && grid[r + 1][c] == '.')
                        dsu.Merge(idx, ToIndex(r + 1, c));
                    if (c - 1 >= 0 && grid[r][c - 1] == '.')
                        dsu.Merge(idx, ToIndex(r, c - 1));
                    if (c + 1 < W && grid[r][c + 1] == '.')
                        dsu.Merge(idx, ToIndex(r, c + 1));
                }
                if (grid[r][c] == 'S')
                {
                    sr = r;
                    sc = c;
                }
            }
        }

        List<int> starts = new List<int>();
        if(sr + 1 < H && grid[sr + 1][sc] == '.')
            starts.Add(ToIndex(sr + 1, sc));
        if (sr - 1 >= 0 && grid[sr - 1][sc] == '.')
            starts.Add(ToIndex(sr - 1, sc));
        if (sc + 1 < W && grid[sr][sc + 1] == '.')
            starts.Add(ToIndex(sr, sc + 1));
        if (sc - 1 >= 0 && grid[sr][sc - 1] == '.')
            starts.Add(ToIndex(sr, sc - 1));

        bool yes = false;
        for (int a = 0; a < starts.Count; a++)
        {
            for (int b = a + 1; b < starts.Count; b++)
            {
                if (dsu.Same(starts[a], starts[b]))
                    yes = true;
            }
        }
        Console.WriteLine(yes ? "Yes" : "No");
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] hw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int H = hw[0];

int W = hw[1];

char[][] grid = new char[H][];

for (int r = 0; r < H; r++)

grid[r] = Console.ReadLine().ToArray();

int ToIndex(int r, int c) => r * W + c;

Dsu dsu = new Dsu(H * W);

int sr = 0;

int sc = 0;

for (int r = 0; r < H; r++)

{

for (int c = 0; c < W; c++)

{

int idx = ToIndex(r, c);

if (grid[r][c] == '.')

{

if (r - 1 >= 0 && grid[r - 1][c] == '.')

dsu.Merge(idx, ToIndex(r - 1, c));

if (r + 1 < H && grid[r + 1][c] == '.')

dsu.Merge(idx, ToIndex(r + 1, c));

if (c - 1 >= 0 && grid[r][c - 1] == '.')

dsu.Merge(idx, ToIndex(r, c - 1));

if (c + 1 < W && grid[r][c + 1] == '.')

dsu.Merge(idx, ToIndex(r, c + 1));

}

if (grid[r][c] == 'S')

{

sr = r;

sc = c;

}

List<int> starts = new List<int>();

if(sr + 1 < H && grid[sr + 1][sc] == '.')

starts.Add(ToIndex(sr + 1, sc));

if (sr - 1 >= 0 && grid[sr - 1][sc] == '.')

starts.Add(ToIndex(sr - 1, sc));

if (sc + 1 < W && grid[sr][sc + 1] == '.')

starts.Add(ToIndex(sr, sc + 1));

if (sc - 1 >= 0 && grid[sr][sc - 1] == '.')

starts.Add(ToIndex(sr, sc - 1));

bool yes = false;

for (int a = 0; a < starts.Count; a++)

{

for (int b = a + 1; b < starts.Count; b++)

{

if (dsu.Same(starts[a], starts[b]))

yes = true;

}

Console.WriteLine(yes ? "Yes" : "No");

}

Blackout 2

問題の概要

N 個の都市と M 個の発電所がある。電線が E 本あり、都市や発電所を繋いでいる。
Q 個のイベントが起きる。
i 番目のイベントでは電線 X[i] が切れ、その電線を辿ることができなくなる。一度切れた電線は、その後も切れたままである。
各イベント直後の電気が通っている都市の数を求めよ。

連結ではなく切断の処理はイベントを逆順にして考えていけばよいことはすぐわかります。問題は TLE しないように各発電所と連結している都市の数を数えるにはどうすればいいかです。

もうひとつさらに頂点（大発電所）を追加してこれとすべての発電所と merge します。そして大発電所とつながっている都市の数を数えれば TLE することなく数えることができます。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nme = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nme[0];
        int M = nme[1];
        int E = nme[2];

        (int, int)[] UV = new (int, int)[E];
        for (int i = 0; i < E; i++)
        {
            int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = uv[0] - 1;
            int v = uv[1] - 1;
            UV[i] = (u, v);
        }

        bool[] B = new bool[E]; // true ならその電線は切れている
        List<int> X = new List<int>();

        int Q = int.Parse(Console.ReadLine());
        for (int i = 0; i < Q; i++)
        {
            int x = int.Parse(Console.ReadLine()) - 1;
            B[x] = true;
            X.Add(x);
        }
        X.Reverse();

        Dsu dsu = new Dsu(N + M + 1);

        // 大発電所と各発電所を繋ぐ
        for (int i = N; i < N + M; i++)
            dsu.Merge(i, N + M);

        // 切れていない電線を繋ぐ
        for (int i = 0; i < E; i++)
        {
            if (!B[i])
                dsu.Merge(UV[i].Item1, UV[i].Item2);
        }

        // 切れている電線を逆順で繋いでいく。通電している都市の数を数える
        List<int> ans = new List<int>();
        foreach (var x in X)
        {
            ans.Add(dsu.Size(N + M) - M - 1);
            dsu.Merge(UV[x].Item1, UV[x].Item2);
        }

        // 解を逆順にして出力
        ans.Reverse();
        foreach (int v in ans)
            Console.WriteLine(v);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nme = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nme[0];

int M = nme[1];

int E = nme[2];

(int, int)[] UV = new (int, int)[E];

for (int i = 0; i < E; i++)

{

int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uv[0] - 1;

int v = uv[1] - 1;

UV[i] = (u, v);

}

bool[] B = new bool[E]; // true ならその電線は切れている

List<int> X = new List<int>();

int Q = int.Parse(Console.ReadLine());

for (int i = 0; i < Q; i++)

{

int x = int.Parse(Console.ReadLine()) - 1;

B[x] = true;

X.Add(x);

}

X.Reverse();

Dsu dsu = new Dsu(N + M + 1);

// 大発電所と各発電所を繋ぐ

for (int i = N; i < N + M; i++)

dsu.Merge(i, N + M);

// 切れていない電線を繋ぐ

for (int i = 0; i < E; i++)

{

if (!B[i])

dsu.Merge(UV[i].Item1, UV[i].Item2);

}

// 切れている電線を逆順で繋いでいく。通電している都市の数を数える

List<int> ans = new List<int>();

foreach (var x in X)

{

ans.Add(dsu.Size(N + M) - M - 1);

dsu.Merge(UV[x].Item1, UV[x].Item2);

}

// 解を逆順にして出力

ans.Reverse();

foreach (int v in ans)

Console.WriteLine(v);

}

E – Graph Destruction

問題の概要

N 頂点 M 辺の単純な無向グラフが与えられる。
頂点 1, 2, …, N を順番に消していったとき、グラフはそれぞれの段階でいくつの連結成分に分かれているか答えよ。

消していく問題なので逆順にして処理をしていけばよいです。連結成分の個数を高速で数えるには、前の段階との差分を考えるとよいです。頂点を追加すると連結成分の個数は 1 増えます。連結成分が merge されると 1 回につき 1 減ります。また merge できるかどうかは追加した頂点と隣接している頂点の番号を比較すればわかります。後者のほうが大きい場合はすでにその頂点は追加されているので merge 可能です。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nme = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nme[0];
        int M = nme[1];

        List<int>[] E = new List<int>[N];

        for (int i = 0; i < N; i++)
            E[i] = new List<int>();

        for (int i = 0; i < M; i++)
        {
            int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = ab[0] - 1;
            int b = ab[1] - 1;
            E[a].Add(b);
            E[b].Add(a);
        }

        List<int> ans = new List<int>();

        Dsu dsu = new Dsu(N);
        int cnt = 0; // 現在の連結成分の個数

        for (int i = N - 1; i >= 0; i--)
        {
            ans.Add(cnt);

            cnt++;

            foreach (var next in E[i])
            {
                // すでに i に隣接する頂点が追加されていて異なる連結成分に属するときは merge する
                if(next > i && !dsu.Same(i, next))
                {
                    dsu.Merge(i, next);
                    cnt--;
                }
            }
        }
        ans.Reverse();
        foreach (var v in ans)
            Console.WriteLine(v);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nme = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nme[0];

int M = nme[1];

List<int>[] E = new List<int>[N];

for (int i = 0; i < N; i++)

E[i] = new List<int>();

for (int i = 0; i < M; i++)

{

int[] ab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int a = ab[0] - 1;

int b = ab[1] - 1;

E[a].Add(b);

E[b].Add(a);

}

List<int> ans = new List<int>();

Dsu dsu = new Dsu(N);

int cnt = 0; // 現在の連結成分の個数

for (int i = N - 1; i >= 0; i--)

{

ans.Add(cnt);

cnt++;

foreach (var next in E[i])

{

// すでに i に隣接する頂点が追加されていて異なる連結成分に属するときは merge する

if(next > i && !dsu.Same(i, next))

{

dsu.Merge(i, next);

cnt--;

}

ans.Reverse();

foreach (var v in ans)

Console.WriteLine(v);

}

E – Just one

問題の概要

N 頂点 M 辺の単純無向グラフが与えられる。
このグラフの M 本の辺すべてに向き付けをする方法は 2^M 通り考えられるが、そのうちどの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在するような向き付けの方法は何通りあるか数え上げよ。
998244353 で割った余りを出力すること。

「どの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在する」という条件を満たすことができない場合とはどのような場合でしょうか？もし連結成分内の頂点と辺の数が一致しないのであれば絶対にできません。一致する場合は連結成分がサイクルグラフになっているか、サイクルグラフから木が生えたグラフになので条件を満たすことができます。この場合、サイクルグラフのなかで右回りと左回りの 2 通りが存在します。

なので解は、すべての連結成分内の頂点と辺の数が一致する場合は 2 の (連結成分の個数)乗であり、そうでない場合は 0 です。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nme = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nme[0];
        int M = nme[1];

        Dsu dsu = new Dsu(N);
        List<int>[] E = new List<int>[N];

        for (int i = 0; i < N; i++)
            E[i] = new List<int>();

        for (int i = 0; i < M; i++)
        {
            int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = uv[0] - 1;
            int v = uv[1] - 1;
            E[u].Add(v);
            E[v].Add(u);
            dsu.Merge(u, v);
        }

        long ans = 1;
        long mod = 998244353;

        foreach (int[] group in dsu.Groups())
        {
            int cnt = 0; // 頂点の次数の総和 / 2 が 辺の数 である
            foreach (var v in group)
                cnt += E[v].Count;

            if (cnt / 2 == group.Length)
            {
                ans *= 2;
                ans %= mod;
            }
            else
            {
                ans = 0;
                break;
            }
        }
        Console.WriteLine(ans);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nme = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nme[0];

int M = nme[1];

Dsu dsu = new Dsu(N);

List<int>[] E = new List<int>[N];

for (int i = 0; i < N; i++)

E[i] = new List<int>();

for (int i = 0; i < M; i++)

{

int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uv[0] - 1;

int v = uv[1] - 1;

E[u].Add(v);

E[v].Add(u);

dsu.Merge(u, v);

}

long ans = 1;

long mod = 998244353;

foreach (int[] group in dsu.Groups())

{

int cnt = 0; // 頂点の次数の総和 / 2 が辺の数である

foreach (var v in group)

cnt += E[v].Count;

if (cnt / 2 == group.Length)

{

ans *= 2;

ans %= mod;

}

else

{

ans = 0;

break;

}

Console.WriteLine(ans);

}

Sum of Maximum Weights

問題の概要

N 頂点の木があり、i 番目の辺は頂点 u[i] と頂点 v[i] を結び、重みは w[i] である。
異なる頂点 u, v に対し、頂点 u から頂点 v までの最短パスに含まれる辺の重みの最大値を f(u, v) と定義する。
異なるすべての 2 頂点における f(i, j) の総和を求めよ。

f(u, v) = w[i] となるための条件について考えます。頂点 u, v を結ぶパスに辺 i が含まれ、かつそのパスに含まれる他の辺の重みが w[i] より小さいことがその条件になります。

そこで辺を重みが小さい順にソートして頂点を merge していきます。u[i] と v[i] が merge される直前において頂点 u[i] が属する連結成分に属する頂点と頂点 v[i] が属する連結成分が属する頂点間の最短パスに含まれる辺の重みの最大値は w[i] と一致します。

なので、w[i] × u[i] が属する連結成分の大きさ × v[i] が属する連結成分の総和が求めるべき解となります。

using AtCoder;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        List<(int, int, int)> E = new List<(int, int, int)>();
        for (int i = 0; i < N - 1; i++)
        {
            int[] uvw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = uvw[0] - 1;
            int v = uvw[1] - 1;
            int w = uvw[2];
            E.Add((u, v, w));
        }

        E = E.OrderBy(_ => _.Item3).ToList();

        long ans = 0;

        Dsu dsu = new Dsu(N);
        foreach (var edge in E)
        {
            if (!dsu.Same(edge.Item1, edge.Item2))
            {
                ans += 1L * dsu.Size(edge.Item1) * dsu.Size(edge.Item2) * edge.Item3;
                dsu.Merge(edge.Item1, edge.Item2);
            }
        }
        Console.WriteLine(ans);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

List<(int, int, int)> E = new List<(int, int, int)>();

for (int i = 0; i < N - 1; i++)

{

int[] uvw = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uvw[0] - 1;

int v = uvw[1] - 1;

int w = uvw[2];

E.Add((u, v, w));

}

E = E.OrderBy(_ => _.Item3).ToList();

long ans = 0;

Dsu dsu = new Dsu(N);

foreach (var edge in E)

{

if (!dsu.Same(edge.Item1, edge.Item2))

{

ans += 1L * dsu.Size(edge.Item1) * dsu.Size(edge.Item2) * edge.Item3;

dsu.Merge(edge.Item1, edge.Item2);

}

Console.WriteLine(ans);

}

E – 1 or 2

問題の概要

整数 N と整数の組 (x, y, z) が M 組与えられる。
1 or 2 が書かれた N 枚のカードがあり、「x 番目のカード + y 番目のカード + z は偶数である」ことがわかっている。
1 のコストを払うことで 1 枚のカードに書かれている整数を知ることができる。
最小で何コスト払えば、すべてのカードに書かれた数を特定することができるだろうか？

x 番目のカードに書かれている数がわかれば y 番目のカードに書かれている数も特定できます。x, y を merge していけば連結成分の個数がコストの最小値となります。

using AtCoder;

class Program
{
    static void Main()
    {
        int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nm[0];
        int M = nm[1];

        Dsu dsu = new Dsu(N);

        for (int i = 0; i < M; i++)
        {
            int[] xyz = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = xyz[0] - 1;
            int v = xyz[1] - 1;
            int w = xyz[2];
            dsu.Merge(u, v);
        }
        Console.WriteLine(dsu.Groups().Length);
    }
}

using AtCoder;

class Program

{

static void Main()

{

int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nm[0];

int M = nm[1];

Dsu dsu = new Dsu(N);

for (int i = 0; i < M; i++)

{

int[] xyz = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = xyz[0] - 1;

int v = xyz[1] - 1;

int w = xyz[2];

dsu.Merge(u, v);

}

Console.WriteLine(dsu.Groups().Length);

}

AtCoder NoviStepsを埋めてみる(15) Union-Find 1Q

C – チームの旗の色

E – Reachability Query

D – Decayed Bridges

E – K-th Largest Connected Components

E – Good Graph

E – Round Trip

Blackout 2

E – Graph Destruction

E – Just one

Sum of Maximum Weights

E – 1 or 2

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ