[Java]白準11724号/接続要素数
質問する
方向図があるかどうかは、接続要素の数を計算するプログラムを作成します.
入力
第1行は、頂点の個数Nと、幹線の個数Mとを与える.(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N−1)/2)2行目から、幹線の両端点uおよびvがM行に与えられる.(1≦u,v≦N,u≠v)のような幹線は一度しか与えられない.
しゅつりょく
接続要素の数を最初の行に出力します.
Key Point
1.既存のDFSソースで解決できる問題.dfsを呼び出すfor文では、kの値範囲設定が間違っているため、エラーとして表示されます.開始点と値の範囲に注意してください.
コード#コード#
https://binghedev.tistory.com/5
方向図があるかどうかは、接続要素の数を計算するプログラムを作成します.
入力
第1行は、頂点の個数Nと、幹線の個数Mとを与える.(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N−1)/2)2行目から、幹線の両端点uおよびvがM行に与えられる.(1≦u,v≦N,u≠v)のような幹線は一度しか与えられない.
しゅつりょく
接続要素の数を最初の行に出力します.
Key Point
1.既存のDFSソースで解決できる問題.dfsを呼び出すfor文では、kの値範囲設定が間違っているため、エラーとして表示されます.開始点と値の範囲に注意してください.
コード#コード#
/*
* 문제 번호 : 11724 (연결 요소의 개수)
* 문제 푼날 : 2022/01/30
*/
import java.io.IOException;
import java.util.Scanner;
public class DFS3 {
static int[][] check; // 간선 연결 상태
static boolean[] checked; // 확인 여부
static int n; // 정점 개수
static int m; // 간선 개수
// 시작점을 변수로 받아 출발, 출력 후 다음 연결점을 찾아 시작점을 변경하여 재호출
public static void dfs(int i) {
checked[i] = true;
for(int j = 1; j <= n; j++) {
if(check[i][j] == 1 && !checked[j]) {
dfs(j);
}
}
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); // 정점 개수
m = sc.nextInt(); // 간선 개수
check = new int[1001][1001]; // 좌표를 그대로 받아들이기 위해 +1해서 선언
checked = new boolean[1001]; // 초기값 False
// 간선 연결상태 저장
for(int i = 0; i < m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
check[u][v] = check[v][u] = 1;
}
int count = 0; // 결과값
for(int k=1; k <= n; k++) { // 0이라는 점이 없으므로 k는 1에서 출발, k는 n보다 작거나 같아야 함!
if(!checked[k]) {
dfs(k);
count++;
}
}
System.out.print(count);
}
}
リファレンスhttps://binghedev.tistory.com/5
Reference
この問題について([Java]白準11724号/接続要素数), 我々は、より多くの情報をここで見つけました https://velog.io/@juwonlee920/Java-백준-11724번-연결-요소의-개수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol