1717번: 집합의 표현
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는
www.acmicpc.net
union-find를 사용해볼 수 있는 문제입니다.
합집합 연산은 0 a b 형태로 주어지고, a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합친다는 의미입니다.
두 집합이 같은 집합인지 확인하는 연산은 1 a b 형태로 주어지고, a와 b가 같은 집합이면 YES, 아니면 NO를 출력하는 문제입니다.
저는 일단 parent배열에 집합의 루트를 자신으로 저장해놓고, union_find를 통해 a의 루트와 b의 루트를 찾아서
합치거나, 같은 집합인지 확인하였습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int parent[] = new int[1000001]; static int N, M; static int find(int v) { if (parent[v] == v) return v; return parent[v] = find(parent[v]); } static void union(int u, int v) { int a = find(u); int b = find(v); if (parent[a] != parent[b]) parent[b] = parent[a]; } static void func() throws Exception { StringBuffer sb = new StringBuffer(); int type, u, v; while (M-- > 0) { st = new StringTokenizer(br.readLine()); type = Integer.parseInt(st.nextToken()); u = Integer.parseInt(st.nextToken()); v = Integer.parseInt(st.nextToken()); if (type == 0) union(Math.min(u, v), Math.max(u, v)); else { if (find(u) == find(v)) sb.append("YES\n"); else sb.append("NO\n"); } } System.out.print(sb.toString()); } static void init() { for (int i = 1; i <= N; i++) { parent[i] = i; } } static void input() throws Exception { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); } public static void main(String[] args) throws Exception { input(); init(); func(); } } | cs |
'algorithm > Union-Find' 카테고리의 다른 글
| boj 20040 사이클 게임 (0) | 2021.06.27 |
|---|---|
| boj 1043 거짓말 (0) | 2021.04.05 |
| boj 10775 공항 (0) | 2021.03.17 |
| boj 4195 친구 네트워크 (0) | 2021.03.17 |
| boj 1976 여행 가자 (0) | 2021.03.17 |