[백준 20040] 사이클 게임

백준 20040번 : 사이클 게임

www.acmicpc.net/problem/20040

20040번: 사이클 게임

---

/* 문제 설명 */

n개의 점이 있고 m개의 쿼리가 있을 때, 사이클의 생성 유무를 구하시오.(n ≤ 500,000 , m ≤ 1,000,000) 

 

/* 해결 방안 */

m개의 쿼리에 대해서 매번 사이클 유무를 판별하기 위해서 BFS, DFS를 수행한다면 시간초과가 난다.따라서 다른 방법을 생각해봐야하는데, 'A와 B의 선분을 이어주는 것'을 'A가 포함된 집합에 B집합을 합집합'하는 것이라고 관점을 바꿔보자. 그러면 Union-find 풀이가 떠오르게 된다.

 

각 쿼리마다 입력되는 A, B 에 대해서 union 연산을 수행하다가, 둘이 이미 같은 집합에 있어서 union이 False를 반환하는 경우에 사이클이 처음 생기게 된다. 따라서 ans에 다가 값을 넣어주자.

 

/* 구현 과정 */

1. 각 쿼리에 대해서 union 연산을 수행한다.

2. find 연산을 통해, 각각의 부모를 찾아주고 만약 둘이 같은 부모를 가지고 있으면(같은 집합이라면) False를 반환한다.

3. ans에다가 값을 넣어준다.

 

 

/* 소스 코드 */

 

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define mod 10007
typedef long long ll;
typedef pair<int, int>pi;
typedef pair<int, pi>pii;

int n, m, ans;
vector<int>parent(500005, -1);

//부모를 찾음
int find(int a) {
	if (parent[a] < 0) return a;
	return parent[a] = find(parent[a]);
}

//union 연산
bool merge(int a, int b) {
	int x = find(a);
	int y = find(b);

	if (x == y) return 0;
	if (parent[x] == parent[y]) parent[x]--;

	if (parent[x] < parent[y]) parent[y] = x;
	else parent[x] = y;
	return 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
      	//이미 사이클을 찾아서 ans가 0이 아닌 경우
		if (ans != 0) continue;
        //둘이 이미 같은 집합에 있어서 union이 False를 반환한 경우 → 사이클 
		if (!merge(a, b)) ans = i;
	}
	cout << ans;
}

 

/* 얻어갈 점 */

1. union-find에서 최적화하도록 코드를 짜는데, 이 때 if(parent[x]==parent[y]) parent[x]--; 는 둘의 rank가 같아서 한 쪽의 rank를 높여주는 거고, 그 다음 조건문에서 높이가 낮은 쪽을 높이가 높은 쪽에다가 합쳐준다. 

2. 이 때, 여기서 -x가 집합의 개수가 아니라 rank라는 걸 까먹지 말자.

 

 

---