https://www.acmicpc.net/problem/4803
문제
그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다.
트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.
그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 n ≤ 500과 m ≤ n(n-1)/2을 만족하는 정점의 개수 n과 간선의 개수 m이 주어진다.
다음 m개의 줄에는 간선을 나타내는 두 개의 정수가 주어진다. 같은 간선은 여러 번 주어지지 않는다.
정점은 1번부터 n번까지 번호가 매겨져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다.
출력
입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다.
예제 입력 1
**6 3**
1 2
2 3
3 4
**6 5**
1 2
2 3
3 4
4 5
5 6
**6 6**
1 2
2 3
1 3
4 5
5 6
6 4
0 0
예제 출력 1
Case 1: A forest of 3 trees.
Case 2: There is one tree.
Case 3: No trees.
풀이
- 입력이 지저분한 문제
- cyclic 여부를 통해 트리인지 아닌지 구분해야 함
- 이전 노드에 대한 정보를 통해 cyclic 판단을 함
package tree;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main_4803 {
private static int testCase = 1;
private static int numberOfNode;
private static int numberOfEdge;
private static int countOfTree;
private static boolean hasNextTestCase = true;
private static boolean isCyclic;
private static boolean[] visited;
private static ArrayList<Integer>[] adjacencyList;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
while (hasNextTestCase) {
input();
process();
testCase++;
}
output();
}
private static void input() throws IOException {
st = new StringTokenizer(br.readLine());
numberOfNode = Integer.parseInt(st.nextToken());
numberOfEdge = Integer.parseInt(st.nextToken());
if (numberOfNode == 0 && numberOfEdge == 0) {
hasNextTestCase = false;
return;
}
visited = new boolean[numberOfNode + 1];
adjacencyList = new ArrayList[numberOfNode + 1];
for (int i = 1; i <= numberOfNode; i++) {
adjacencyList[i] = new ArrayList<>();
}
for (int i = 0; i < numberOfEdge; i++) {
st = new StringTokenizer(br.readLine());
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
adjacencyList[node1].add(node2);
adjacencyList[node2].add(node1);
}
}
private static void process() {
if (!hasNextTestCase) {
return;
}
countOfTree = 0;
for (int node = 1; node <= numberOfNode; node++) {
if (visited[node]) {
continue;
}
isCyclic = false;
dfs(node, -1);
if (!isCyclic) {
countOfTree++;
}
}
updateResult();
}
private static void dfs(int node, int previousNode) {
visited[node] = true;
for (Integer nextNode : adjacencyList[node]) {
if (nextNode == previousNode) {
continue;
}
if (nextNode != previousNode && visited[nextNode]) {
isCyclic = true;
return;
}
dfs(nextNode, node);
}
}
private static void updateResult() {
if (countOfTree == 0) {
sb.append("Case " + testCase + ": No trees.").append('\n');
}
if (countOfTree == 1) {
sb.append("Case " + testCase + ": There is one tree.").append('\n');
}
if (countOfTree >= 2) {
sb.append("Case " + testCase + ": A forest of " + countOfTree + " trees.").append('\n');
}
}
private static void output() {
System.out.println(sb);
}
}