演習課題「連結成分の要素」
頂点数 n, 辺数 m のグラフが与えられるので、各連結成分に含まれる要素を連結成分ごとにリストで求め、それらをすべてまとめた「リストのリスト」を求めるプログラムを完成させてください。
制約
・ 入力はすべて整数
・ 1 ≦ n ≦ 10
・ 頂点の番号は 1 以上 n 以下
期待する出力値
[ 1 2 4 5 ]
[ 3 ]
＃07:連結成分
このチャプターでは、深さ優先探索を利用して連結成分の個数を求めるプログラムを作成します。
準備：
・訪問済みかどうかを記録する配列を未訪問で初期化
関数 dfs：
・頂点 v を訪問済みにする
・隣接する頂点を順番に見て、もし未訪問であれば dfs を呼び出す
関数 connectedComponents：
・個数を数えるための変数を用意
・すべての頂点を順番に見て、もし未訪問であれば dfs を呼び出して個数を 1 増やす
・個数を返す
5 5
1 2
2 3
3 4
4 5
5 25 3
1 2
3 4
4 5
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.ArrayDeque;
public class Main {
static List<List<Integer>> g;
// 訪問済みかどうかを記録する配列 visited を用意
static boolean[] visited;
static void dfs(int v) {
// 頂点 v を訪問済みにする
visited[v] = true;
// 頂点 v に隣接するすべての頂点 u について
for (int u : g.get(v)) {
// 頂点 u が訪問済みでなければ
if (!visited[u]) {
// 頂点 u に対して dfs を呼び出す
dfs(u);
}
}
}
static int connectedComponents(int n) {
// visited を未訪問で初期化
visited = new boolean[n];
// 連結成分の個数を数えるための変数 cnt を 0 で初期化
int cnt = 0;
// 頂点を 1 つひとつ順番に見ていく
for (int i = 0; i < n; i++) {
// 頂点 i が訪問済みでなければ
if (!visited[i]) {
// 頂点 i に対して dfs を呼び出す
dfs(i);
// 連結成分の個数を 1 つ増やす
cnt++;
}
}
// 連結成分の個数 cnt を返す
return cnt;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
g = new ArrayList<List<Integer>>(n);
for (int i = 0; i < n; i++) {
g.add(new ArrayList<Integer>());
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
g.get(a).add(b);
g.get(b).add(a);
}
System.out.println("連結成分は " + connectedComponents(n) + " 個です");
sc.close();
}
}