[백준] B20040 사이클 게임

union-find 문제

문제

입력으로 점의 개수 n과 m 번째 차례까지의 게임 진행 상황이 주어지면 사이클이 완성 되었는지를 판단하고, 완성되었다면 몇 번째 차례에서 처음으로 사이클이 완성된 것인지를 출력하는 프로그램을 작성하시오.

C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다.

입력
노드개수 n (3 ≤ n ≤ 500,000)과 진행된 차례의 수를 나타내는 정수 3 ≤ m ≤ 1,000,000 이 주어진다.

출력
입력으로 주어진 케이스에 대해, m 번째 차례까지 게임을 진행한 상황에서 이미 게임이 종료되었다면 사이클이 처음으로 만들어진 차례의 번호를 양의 정수로 출력하고, m 번의 차례를 모두 처리한 이후에도 종료되지 않았다면 0을 출력한다.

풀이

노드 n개와 간선 m개가 주어진 상황에서 순서대로 간선을 추가해나가며 사이클이 생성된 시기를 출력하는 문제이다.

m개의 간선이 차례대로 추가되는데 i번째 단계에서만 조건을 넣어 사이클 생성 여부를 판단해야 한다.

서로 다른 집합에 속해 있는 노드를 연결하는 간선의 경우, 아래의 그림처럼 두 집합을 이어주는 역할만을 할 뿐 사이클을 생성하지 못한다.

따라서 동일한 집합에 속해있는 두 노드 사이에 간선을 추가하게 될 경우 사이클이 생성되는데 이에 맞는 union-find 자료구조를 사용해준다.

---

i번째로 추가되는 두 노드를 잇는 간선을 a-b라고 하겠다.

1. a가 속한 집합의 대표 노드와 b가 속한 집합의 대표 노드 찾기
   • find(x) 함수를 통해 x노드가 속한 집합의 대표 노드를 찾게 되는데, 이 과정에서 경로 압축을 해주어야 최적화가 가능하다.
   • 경로 압축: x 노드에서 대표 노드까지 가는 경로 상의 모든 노드가 대표 노드를 가리키도록 처리해준다.
2. 사이클 발생여부 판단
   • rootA와 rootB가 동일할 경우, 같은 집합에 속한 두 노드이므로 간선이 추가되면 사이클이 발생한다.
     문제에서는 처음 사이클이 발생한 경우를 찾아야하므로 사이클 발생 시기를 기억하는 변수를 추가하여 처리해준다.
   • rootA와 rootB가 동일하지 않을 경우, 작은 집합의 대표 노드가 더 큰 집합의 대표 노드를 가리키도록 해준다. (두 집합 합치기)
3. 1~2 과정 m회 반복

---

코드

//B20040 사이클게임 [골4]
#include<iostream>
#include<vector>

using namespace std;

class Union {
private:
	//데이터 저장 배열
	vector<int> parent;
	//노드 개수
	int n;
	//사이클 생성 시기
	int count;

public:
	//생성자
	Union(int n) {
		this->n = n;
		parent.resize(n, -1);
		count = 0;
	}

	void print() {
		for (int i = 0;i < n;i++) {
			cout << parent[i] << " ";
		}
		cout << endl;
	}

	int find(int key) {
		//루트 노드 찾기
		if (parent[key] < 0) {
			//cout<<key<<endl;
			return key;
		}
		else {
			//cout<<"경로 압축"<<endl;
			return parent[key] = find(parent[key]);
		}
	}

	bool push(int a, int b) {
		//간선 추가
		//a와 b가 같은 집합에 속하는지 확인
		//같은 집합이면 사이클 발생
		//다른 집합이면 더 큰 집합으로 합치기
		
		int rootA = find(a);
		int rootB = find(b);

		//cout<<rootA<<" "<<rootB<<endl;
		
		if(rootA == rootB) {
			//같은 집합
			return true;
		}
		
		//다른 집합일 경우 연결
		if (parent[rootA] < parent[rootB]) {
			//rootA가 더 큰 집합
			parent[rootA] += parent[rootB];
			parent[rootB] = rootA;
		}
		else {
			//rootB가 더 큰 집합
			parent[rootB] += parent[rootA];
			parent[rootA] = rootB;
		}
		return false;
	}	

	int getCount() {
		return count;
	}

	void setCount(int v) {
		count = v;
	}
};

int main(void) {
	int n, m;

	cin >> n >> m;
	//n : 노드 개수
	//m : 에지 개수

	Union u(n);

	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		if (u.push(a, b)&&u.getCount()==0) {
			//cout<<i+1;
			//cout << "사이클 발생" << endl;
			u.setCount( i + 1);
		}
		//u.print();
		//cout << u.getCount();
	}

	cout<<u.getCount();

	return 0;
}