์ ์ข ๋ฐ์ด๋ฌ์ค์ธ ์ ๋ฐ์ด๋ฌ์ค๋ ๋คํธ์ํฌ๋ฅผ ํตํด ์ ํ๋๋ค. ํ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ๊ทธ ์ปดํจํฐ์ ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ ๋ชจ๋ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค.
์๋ฅผ ๋ค์ด 7๋์ ์ปดํจํฐ๊ฐ <๊ทธ๋ฆผ 1>๊ณผ ๊ฐ์ด ๋คํธ์ํฌ ์์์ ์ฐ๊ฒฐ๋์ด ์๋ค๊ณ ํ์. 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๋ฉด ์ ๋ฐ์ด๋ฌ์ค๋ 2๋ฒ๊ณผ 5๋ฒ ์ปดํจํฐ๋ฅผ ๊ฑฐ์ณ 3๋ฒ๊ณผ 6๋ฒ ์ปดํจํฐ๊น์ง ์ ํ๋์ด 2, 3, 5, 6 ๋ค ๋์ ์ปดํจํฐ๋ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ค. ํ์ง๋ง 4๋ฒ๊ณผ 7๋ฒ ์ปดํจํฐ๋ 1๋ฒ ์ปดํจํฐ์ ๋คํธ์ํฌ์์์ ์ฐ๊ฒฐ๋์ด ์์ง ์๊ธฐ ๋๋ฌธ์ ์ํฅ์ ๋ฐ์ง ์๋๋ค.
์ด๋ ๋ 1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ๋ค. ์ปดํจํฐ์ ์์ ๋คํธ์ํฌ ์์์ ์๋ก ์ฐ๊ฒฐ๋์ด ์๋ ์ ๋ณด๊ฐ ์ฃผ์ด์ง ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์๋ ์ปดํจํฐ์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ปดํจํฐ์ ์๋ 100 ์ดํ์ด๊ณ ๊ฐ ์ปดํจํฐ์๋ 1๋ฒ ๋ถํฐ ์ฐจ๋ก๋๋ก ๋ฒํธ๊ฐ ๋งค๊ฒจ์ง๋ค. ๋์งธ ์ค์๋ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ ์์ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ด์ด์ ๊ทธ ์๋งํผ ํ ์ค์ ํ ์์ฉ ๋คํธ์ํฌ ์์์ ์ง์ ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ์ ๋ฒํธ ์์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
1๋ฒ ์ปดํจํฐ๊ฐ ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ ธ์ ๋, 1๋ฒ ์ปดํจํฐ๋ฅผ ํตํด ์ ๋ฐ์ด๋ฌ์ค์ ๊ฑธ๋ฆฌ๊ฒ ๋๋ ์ปดํจํฐ์ ์๋ฅผ ์ฒซ์งธ ์ค์ ์ถ๋ ฅํ๋ค.
๐ก ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋ ์ปดํจํฐ๋ฅผ ๊ฐ๊ฐ list์ ๋ฃ์ด์ค
๐ก ์ด๋ฏธ ํ์ธํ๋ ์ปดํจํฐ๋ฅผ ์ ์ธ์์ผ stackoverflow๊ฐ ๋์ง ์๊ฒ ํจ
๐ก ์ฐ๊ฒฐ๋์ด ์๋ ์ปดํจํฐ๋ฅผ ํ์ธํ ๋๋ง๋ค, count++ํด์ฃผ์ด ํ ๋คํธ์ํฌ ์์ ์ปดํจํฐ ๊ฐ์ ํ์
ํจ
for(int i=0; i<m; i++) {
String[] s = br.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
computer[a].add(b);
computer[b].add(a);
}
for(int target : computer[virus]) {
if(!visited[target]) {
visited[target] = true;
dfs(target);
}
}
count++;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.ArrayList;
public class Bruteforce_10 {
static List<Integer>[] computer;
static boolean[] visited;
static int count = 0;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
computer = new ArrayList[n+1];
visited = new boolean[n+1];
for(int i=1; i<n+1; i++)
computer[i] = new ArrayList<>();
for(int i=0; i<m; i++) {
String[] s = br.readLine().split(" ");
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
computer[a].add(b);
computer[b].add(a);
}
visited[1] = true;
dfs(1);
System.out.println(count);
}
static void dfs(int virus) {
for(int target : computer[virus]) {
if(!visited[target]) {
visited[target] = true;
count++;
dfs(target);
}
}
}
}
์ฑ๊ณตโจ