[BOJ] 백준 13244번 Tree (Java)

#13244 Tree

난이도 : 골드 4

유형 : 그래프 / 트리 / Union-Find

13244번: Tree

▸ 문제

One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees.

Trees are the subset of graphs that have the following 3 properties:

1. It is connected: for every node you can reach every other node following edges.
2. If an edge is removed, the graph is no longer connected. That is, some nodes cannot be reached anymore.
3. When an edge is added between two existing nodes A and B, a cycle is created. There is a cycle if there is more than one way to go from A to B.

Your task is to decide if a given graph is a tree or not.

▸ 입력

The first line will contain an integer T representing the number of graphs to check. There will be at most 10 graphs in each test case.

Each of the graph will be represented as follows:

The first line will contain an integer N with the number of nodes in the graph. The number of nodes will be between 1 and 1,000. The identifier of each node will be an integer from 1 to N. 

The next line will contain an integer M with the number of edges in the graph. There will be at most 10^6 edges.

The next M lines will contain 2 integers A and B each. These are the two nodes connected by an edge.

The total sum of M in all test cases is at most 10^6.

▸ 출력

For each graph, a single line with “tree” if the graph represents a tree or “graph“ otherwise.

 

문제 풀이  

주어진 정점의 갯수가 간선의 정보로 그래프이냐 트리이냐를 판별하는 문제이다.

1. 싸이클이 있을 경우, 그래프이다.
2. 컴포넌트가 2개 이상일 경우, 그래프이다.
3. 두 정점 사이에 간선의 갯수가 2개 이상일 경우, 그래프이다.
4. 그 외에는 트리라고 판별해도 된다.

 

해당 문제를 풀기 위해서는 Union-Find 서로소 집합 판별 알고리즘을 사용해주면 된다. 주어진 간선을 잇는 두 정점의 정보로 parents 정보를 저장한다. 

1. find(a) == find(b)일 경우, 같은 두 정점을 잇는 간선이 2개 이상(3번)이거나 싸이클이 형성된 것(1번)이므로 그래프로 판별한다.
2. 모든 값 입력이 끝난 후 parents[] 배열의 부모가 2개 이상일 경우 컴포넌트가 2개 이상인 것(2번)이므로 그래프로 판별한다.
3. 그 외에는 트리로 판별한다.

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static int[] parents;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		StringTokenizer st;
		while(t-->0) {
			int n = Integer.parseInt(br.readLine());
			int m = Integer.parseInt(br.readLine());
			
			parents = new int[n+1];
			for(int i=1; i<n+1; i++) {
				parents[i] = i;
			}
			
			boolean flag = false;
			for(int i=0; i<m; i++) {
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				if(find(a)!=find(b)) {
					union(a,b);
				}else {
					flag = true;
				}
			}
			
			Set<Integer> set = new HashSet<Integer>();
			for(int i=1; i<n+1; i++) {
				set.add(find(parents[i]));
			}
			
			if(flag || set.size()>1) {
				System.out.println("graph");
			} else {
				System.out.println("tree");
			}
		}
	}
	static int find(int x) {
		if(parents[x] == x) {
			return x;
		}
		return parents[x]= find(parents[x]);
	}
	
	static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x > y) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		
		parents[y] = x;
	}
}