728x90
๐๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/17352
๐ป์ฝ๋
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
parent = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
parent[i] = i;
}
for (int i = 0; i < N - 2; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
union(x, y);
}
int island1 = 0, island2 = 0;
for (int i = 1; i < N + 1; i++) {
int n = find(i);
if (island1 == 0) {
island1 = n;
} else if (island1 != n && island2 == 0) {
island2 = n;
break;
}
}
System.out.print(island1 + " " + island2);
}
public static boolean union(int x, int y) {
x = find(x); //x์ ๋ถ๋ชจ๋
ธ๋ ์ฐพ๊ธฐ
y = find(y); //y์ ๋ถ๋ชจ๋
ธ๋ ์ฐพ๊ธฐ
// ์ด๋ฏธ ๊ฐ์ ๊ทธ๋ํ์ ์ํด์์ ๋ false ๋ฐํ
if (x == y) return false;
if (x <= y) parent[y] = x;
else parent[x] = y;
return true;
}
public static int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]);
}
}
728x90
'Algorithm > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm/Baekjoon] ํด์ฌ - 14501 (S3/JAVA) (0) | 2025.02.12 |
---|---|
[Algorithm/Baekjoon] ํ๋ถ ์ฐ๊ตฌ์ ๋ฏผ์ - 21922 (G5/JAVA) (2) | 2025.01.20 |
[Algorithm/Baekjoon] ๋๋ฌด ํ์ถ - 15900 (S1/JAVA) (3) | 2024.12.30 |
[Algorithm/Baekjoon] ์ ์ ์ฌ์ - 1946 (S1/JAVA) (1) | 2024.12.23 |
[Algorithm/Baekjoon] ์ ๋ฐ ๋ช ๋จ - 3980(G5/JAVA) (0) | 2024.12.16 |