C - Bridge
はじめに
競技プログラミング、AtCoder Beginner Contest 75
C - Bridge
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
自己ループと二重辺を含まないN頂点M辺の無向連結グラフが与えられます。 i(1≦i≦M)番目の辺は頂点aiと頂点biを結びます。 グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のことを橋と呼びます。 与えられたM本のうち橋である辺の本数を求めてください。 ・自己ループ とは、ai=bi(1≦i≦M)であるような辺iのことをいいます。 ・二重辺 とは、ai=ajかつ bi=bj(1≦i<j≦M)であるような辺の組 i,jのことをいいます。 ・無向グラフが 連結 であるとは、グラフの任意の二頂点間に経路が存在することをいいます。
制約
・2≦N≦50 ・N−1≦M≦min(N(N−1)/2,50) ・1≦ai<bi≦N ・与えられるグラフは自己ループと二重辺を含まない。 ・与えられるグラフは連結である。
入力
入力は以下の形式で標準入力から与えられる。 N M a1 b1 a2 b2 : aM bM
出力
M本の辺のうち、橋である辺の本数を出力せよ。
解き方
以下を参考にしています。
※この記事ではDFSを使用して解いています
https://img.atcoder.jp/abc075/editorial.pdf
提出 #4407450 - AtCoder Beginner Contest 075
この問題で答えるものは
「与えられるM本のうち「橋」がいくつあるか」です。
これを求めるためには、
それぞれの辺が「橋」かどうかを判定し
「橋」と判定されたものの数を数えればできます。
そのため、
どのようにすれば辺を「橋」かどうか判定できるかを考えます。
まず問題文から
「橋」とは
グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のこと
である、ということが分かります。
ここから、
１つの「辺」を取り除いた場合に
全ての頂点を辺を伝って訪問することができなければ
その「辺」は「橋」である
ということが言えそうです。
例えば、
入力例１では
頂点1と頂点3を繋ぐ辺をなくしてしまうと
頂点2,3,4,5,6,7からは辺を伝って頂点1に行くことができなくなるので
頂点1と頂点3を繋ぐ辺が「橋」だということが分かります。
↑頂点1と頂点3を繋ぐ辺を消すと全ての頂点には行き来できなくなる図
辺を一つ取り除き
その状態で各頂点を全て訪問できるかどうかで
辺が「橋」かどうかを判定します。
以下コードを見ながら進みます。
全体のコードは以下です。
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
struct Connection
{
public List<int> list;
public Connection(int index)
{
list = new List<int>();
}
}
static void Main()
{
var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var N = nm[0];
var M = nm[1];
var a = new int[M];
var b = new int[M];
for (int i = 0; i < M; ++i)
{
var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
a[i] = ab[0];
b[i] = ab[1];
}
var ans = 0L;
for (int i = 0; i < M; ++i)
{
var connection = new Connection[N];
for (int j = 0; j < N; ++j) connection[j] = new Connection(j);
for (int j = 0; j < M; ++j)
{
if (i == j) continue;
connection[a[j] - 1].list.Add(b[j] - 1);
connection[b[j] - 1].list.Add(a[j] - 1);
}
var hashSet = new HashSet<int>();
Dfs(hashSet, connection, 0);
if (hashSet.Count() != N) ans++;
}
Console.WriteLine(ans);
}
static void Dfs(HashSet<int> hashSet, Connection[] connection, int index)
{
hashSet.Add(index);
foreach (var l in connection[index].list)
{
if (!hashSet.Contains(l)) Dfs(hashSet, connection, l);
}
}
}
まず入力の格納は以下のようにしています。
var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var N = nm[0];
var M = nm[1];
var a = new int[M];
var b = new int[M];
for (int i = 0; i < M; ++i)
{
var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
a[i] = ab[0];
b[i] = ab[1];
}
辺を一つずつ消して橋かどうか判定しているのは以下の部分です。
//橋の数を入れる変数
var ans = 0L;
//一つずつ辺を消したいのでM回まわす
for (int i = 0; i < M; ++i)
{
//構造体の初期化
//connectionは各頂点の繋がりの情報を入れるもの
//頂点はN個あるのでN個
var connection = new Connection[N];
for (int j = 0; j < N; ++j) connection[j] = new Connection(j);
// i 番目の辺を削除した頂点どうしの繋がりを保存
for (int j = 0; j < M; ++j)
{
// i 番目の辺が繋いでいる頂点の情報は保存しない
if (i == j) continue;
//辺がつなぐ頂点の情報を各頂点のリストに格納する
connection[a[j] - 1].list.Add(b[j] - 1);
connection[b[j] - 1].list.Add(a[j] - 1);
}
//訪問した頂点を格納する
var hashSet = new HashSet<int>();
//DFS
Dfs(hashSet, connection, 0);
//訪問した頂点の数がNと違うなら、
//辺を消すことによって行けなくなった頂点があるということなので橋になる
if (hashSet.Count() != N) ans++;
}
まずループの回数は
辺を一つずつ消していって
各頂点を全て訪問できるかどうかを知りたいので
辺の数と同じM回まわします。
//一つずつ辺を消したいのでM回まわす
for (int i = 0; i < M; ++i)
{
…
}
次に各頂点の情報を入れる
connectionを初期化しています。
頂点の数はN個あるので
ここでは、N個初期化をしています。
//構造体の初期化 //connectionは各頂点の繋がりの情報を入れるもの //頂点はN個あるのでN個 var connection = new Connection[N]; for (int j = 0; j < N; ++j) connection[j] = new Connection(j);
中のループでは i 番目の橋を消したときの
頂点どうしの繋がりを保存しています。
そのため、M回まわしています。
//各辺の頂点の繋がりを保存したいのでM回まわす
for (int j = 0; j < M; ++j)
{
…
}
i 番目の橋を消したときの状態が欲しいので
i 番目の橋の情報は保存しないようにcontinueしています。
// i 番目の辺が繋いでいる頂点の情報は保存しない if (i == j) continue;
connectionは各頂点の情報を入れるようになっていて
listには頂点が辺を通じてどこと繋がっているのか？
という情報を入れるようになっています。
//辺がつなぐ頂点の情報を各頂点のリストに格納する connection[a[j] - 1].list.Add(b[j] - 1); connection[b[j] - 1].list.Add(a[j] - 1);
以下の入力例1を例にすると
7 7 1 3 2 7 3 4 4 5 4 6 5 6 6 7
j ( ループのindex )が 0 のとき
頂点1のconnection[0].listには2
頂点3のconnection[2].listには0
がそれぞれ入ります。
j ( ループのindex )が 1 のとき
頂点2のconnection[1].listには6
頂点7のconnection[6].listには2
がそれぞれ入ります。
これを橋かどうか判定したい辺を除いて繰り返します。
上を見ると分かるように
indexは実際の頂点の番号とは１ずれたものを使用しています。
Dfs関数の中身は以下のようになっています。
static void Dfs(HashSet<int> hashSet, Connection[] connection, int index)
{
//訪問した頂点をhashSetに保存する
hashSet.Add(index);
//connectionのlistに保存してある頂点を順番に訪問する
foreach (var l in connection[index].list)
{
//hashSetに保存されていない頂点はまだ訪問していないので再帰処理をする
if (!hashSet.Contains(l)) Dfs(hashSet, connection, l);
}
}
Dfs関数の中でしていることは以下の２つです。
①訪問した頂点をhashSetに保存する
②connection.listから繋がりのある頂点を取り出し、順番に各頂点を訪問する
各頂点の繋がり追っていけば、
繋がりのある頂点は全てhashSetに保存されます。
Dfs関数を呼んだ後でhashSetにはいくつの頂点が保存されているのかをみれば
情報を保存しなかった辺が橋なのかどうかを判定することができます。
頂点は全部でN個あるので
hashSetにN個の値が入っていなければ
訪問できなかった頂点があるということになるので
情報を保存しなかった辺は橋であるということになります。
最後に橋の数を出力します。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
struct Connection
{
public List<int> list;
public Connection(int index)
{
list = new List<int>();
}
}
static void Main()
{
var nm = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
var N = nm[0];
var M = nm[1];
var a = new int[M];
var b = new int[M];
for (int i = 0; i < M; ++i)
{
var ab = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
a[i] = ab[0];
b[i] = ab[1];
}
//橋の数を入れる変数
var ans = 0L;
//一つずつ辺を消したいのでM回まわす
for (int i = 0; i < M; ++i)
{
//構造体の初期化
//connectionは各頂点の繋がりの情報を入れるもの
//頂点はN個あるのでN個
var connection = new Connection[N];
for (int j = 0; j < N; ++j) connection[j] = new Connection(j);
// i 番目の辺を削除した頂点どうしの繋がりを保存
for (int j = 0; j < M; ++j)
{
// i 番目の辺が繋いでいる頂点の情報は保存しない
if (i == j) continue;
//辺がつなぐ頂点の情報を各頂点のリストに格納する
connection[a[j] - 1].list.Add(b[j] - 1);
connection[b[j] - 1].list.Add(a[j] - 1);
}
//訪問した頂点を格納する
var hashSet = new HashSet<int>();
//DFS
Dfs(hashSet, connection, 0);
//訪問した頂点の数がNと違うなら、
//辺を消すことによって行けなくなった頂点があるということなので橋になる
if (hashSet.Count() != N) ans++;
}
Console.WriteLine(ans);
}
static void Dfs(HashSet<int> hashSet, Connection[] connection, int index)
{
//訪問した頂点をhashSetに保存する
hashSet.Add(index);
//connectionのlistに保存してある頂点を順番に訪問する
foreach (var l in connection[index].list)
{
//hashSetに保存されていない頂点はまだ訪問していないので再帰処理をする
if (!hashSet.Contains(l)) Dfs(hashSet, connection, l);
}
}
}
