[백준][union find] 13244 Tree c++구현

목차

https://www.acmicpc.net/problem/13244

문제

문제 설명

컴퓨터 과학에서 가장 중요한 자료 구조 중 하나는 트리입니다. 이 문제에서는 일반적인 트리에 대해 다룹니다.

트리는 다음 세 가지 속성을 가지는 그래프의 부분 집합입니다:

1. 연결성 (Connected): 모든 노드에 대해, 한 노드에서 다른 모든 노드로 가는 경로가 존재합니다.
2. 간선 제거 시 비연결성 (Edge removal leads to disconnection): 한 간선을 제거하면, 그래프는 더 이상 연결되지 않습니다. 즉, 일부 노드에 도달할 수 없게 됩니다.
3. 간선 추가 시 순환 생성 (Edge addition creates a cycle): 기존의 두 노드 A와 B 사이에 간선을 추가하면 순환이 생성됩니다. 즉, A에서 B로 가는 경로가 두 개 이상 존재하게 됩니다.

입력 형식

• 첫 번째 줄에는 체크할 그래프의 수를 나타내는 정수 T가 주어집니다. 각 테스트 케이스에는 최대 10개의 그래프가 포함됩니다.
• 각 그래프는 다음과 같은 형식으로 제공됩니다:
  • 첫 번째 줄에는 그래프의 노드 수를 나타내는 정수 N이 주어집니다. 노드의 수는 1부터 1,000까지입니다. 각 노드의 식별자는 1부터 N까지의 정수입니다.
  • 다음 줄에는 그래프의 간선 수를 나타내는 정수 M이 주어집니다. 간선의 수는 최대 1,000,000개입니다.
  • 다음 M개의 줄에는 두 개의 정수 A와 B가 주어집니다. 이는 노드 A와 노드 B를 연결하는 간선을 나타냅니다.

제약 조건

• 모든 테스트 케이스의 M의 총합은 최대 1,000,000입니다.

 

 

문제 구현 방향

나는 union find를 통해 트리를 판별해야겠다는 생각이 들었고 parent를 만드는 과정에서

추가할때 부모가 같으면 그래프이고 나머지는 부모가 자기자신이 아니면 부모를 추가해 주는 방식으로 구현했다.

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<queue>

using namespace std;

int T, N, M;



int parent[1002];

//부모를 찾는 함수
int findParent(int a) {
	if (parent[a] == a)
		return a;
    //부모 찾는 시간 단축
	return parent[a] = findParent(parent[a]);
}

//부모를 자기 자신으로 만들어주는 초기화 함수
void init(int N) {
	for (int i = 0; i <= N; i++) {
		parent[i] = i;
	}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> T ;
	int a, b;
	
	for (int i = 0; i < T; i++) {
		cin >> N >> M;
		int treeFlag = 1;
		init(N);
		for (int j = 0; j < M; j++) {
			cin >> a >> b;
            
            //부모가 다를 경우
			if (findParent(a) != findParent(b)) {
				if (findParent(a) == a) {
					parent[a] = b;
				}
				else if (findParent(b) == b) {
					parent[b] = a;
				}
			}
            //부모가 같을 경우
			else {
				treeFlag = 0;
			}
		
		}
        
		int k = findParent(1);
		for (int j = 2; j <= N; j++) {
        	//부모가 다르면 그래프
			if (k != findParent(j)) {
				treeFlag = 0;
				break;
			}
		}
		if (treeFlag) {
			cout << "tree\n";
		}
		else
			cout << "graph\n";
	}

	

}