백준 20040 c++ "사이클 게임" -PlusUltraCode-

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

[필자 사고]

문제를 읽어보면 사이클이 생기냐 안생기냐 를 구분하는 문제이다.

입력이 순서대로 주어질 때 처음으로 사이클이 생기는 경우를 골라야 된다.

필자는 사이클의 유무와 처음으로 사이클이 생기는 경우 이 두가지를 조합하여 유니온 파인드 알고리즘을

사용하여 문제를 해결했다.

[코드 해설]

 

• Union-Find 자료구조의 초기화
  프로그램은 N개의 노드와 M개의 간선 정보를 입력받습니다.
  먼저 parent 벡터를 초기화하여, 각 노드가 자기 자신을 부모로 가지도록 설정합니다.
  이는 각 노드가 독립된 집합으로 시작함을 의미합니다.
• Find 함수
  find 함수는 주어진 노드의 루트 부모를 찾는 역할을 합니다.
  경로 압축(Path Compression)을 통해 탐색 과정에서 부모를 최적화하여 시간 복잡도를 줄입니다.
• Union 함수
  Union 함수는 두 노드를 같은 집합으로 합칩니다.
  이를 위해 두 노드의 루트 부모를 확인한 뒤, 루트가 다르다면 한 쪽의 부모를 다른 쪽으로 설정합니다.
• isSame 함수
  두 노드가 같은 집합에 속해 있는지 확인합니다.
  두 노드의 루트 부모가 같으면 true, 다르면 false를 반환합니다.
• 간선 정보 처리 및 사이클 감지
  입력으로 주어진 M개의 간선 정보를 차례로 처리합니다.
  각 간선을 처리할 때, 연결된 두 노드가 이미 같은 집합에 속해 있는지 확인합니다.
  • 사이클이 없는 경우: 두 노드를 같은 집합으로 합칩니다(Union).
  • 사이클이 발생한 경우: 해당 간선이 추가된 시점을 기록(ans = i + 1)하고 루프를 종료합니다.
• 결과 출력
  사이클이 발생한 간선의 순서를 출력합니다.
  사이클이 없는 경우 ans는 초기값 0으로 유지되어 출력됩니다.

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int ans=0;
vector<int> parent;

int find(int a) {
	if (parent[a] == a) return a;
	return parent[a] = find(parent[a]);
}
void Union(int a, int b) {
	a = find(a);
	b = find(b);

	if (a != b) parent[b] = a;
}
bool isSame(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b)return false;
	return true;
}

void Input() {
	cin >> N >> M;
	parent.resize(N);
	
	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		if (isSame(start, end) == false)Union(start, end);
		else {
			ans = i + 1;
			break;
		}
	}
}

int main(void) {
	Input();
	cout << ans;
}