BOJ 17038 - The great revegetation (유니온 파인드, 이분그래프)

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

그래프가 이분그래프인지 아는법 기록 + 온라인쿼리 풀이 숙지

 

<문제설명>

최대 1e5개의 목초지 n개가 있다고 할 때, 소(쿼리) m개가의 정보가 들어온다.

 

목초지는 두 그룹으로 나뉜다.

 

S a b : a,b목초지가 같은 그룹에 있어야 해.

D a b : a,b목초지가 다른 그룹에 있어야 해.

 

모든 목초지를 나누는 경우의 수를 구하라

 

<풀이>

오프라인 쿼리. s먼저 입력해서 merge해두고 d를 입력받으면서 a,b의 대표값을 간선으로 이어준다.

 

그래프가 이분그래프라면 컴포넌트마다 그룹을 나누는 경우가 두가지이므로 2^컴포넌트의 수가 정답.

 

그래프가 이분그래프가 아니면 그룹을 나눌 수 없다.

 

<코드>

int n, m, uf[MAX], vst[MAX];
vector<int> adj[MAX];
bool fin[MAX],fail=false;

int find(int u) {
	if (uf[u] == -1) return u;
	return uf[u] = find(uf[u]);
}
void merge(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	uf[u] = v;

}
void dfs(int u, int p) {
	vst[u] = vst[p]==1?2:1;

	for (int v : adj[u]) {
		if (v == p) continue;
		if (vst[v] && !fin[v] && vst[v]==vst[u]) fail = true;
		else if (!vst[v]) dfs(v, u);
	}

	fin[u] = true;
}

int main() {
	FAST;
	cin >> n >> m;
	memset(uf, -1, sizeof(uf));
	vector<P> sq,dq;
	for (int i = 0,a,b; i < m; i++) {
		char c;
		cin >> c >> a >> b;
		if (c == 'S') sq.push_back({ a,b });
		if (c == 'D') dq.push_back({ a,b });
	}
	for (int i = 0,a,b; i < sq.size(); i++) {
		tie(a, b) = sq[i];
		merge(a, b);
	}
	for (int i = 0, a, b; i < dq.size(); i++) {
		tie(a, b) = dq[i];
		if (find(a) == find(b)) fail = true; //자기자신으로가는 간선 생각 x
		adj[find(a)].push_back(find(b));
		adj[find(b)].push_back(find(a));
	}

	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (!vst[find(i)]) {
			cnt++;
			dfs(find(i),0);
		}
	}

	if (fail) cout << 0 << '\n';
	else {
		cout << 1;
		while (cnt--) cout << 0;
		cout << '\n';
	}
}

 

<온라인쿼리 풀이> - koosaga님의 코드로 공부해보자

//https://www.acmicpc.net/source/12576994
//koosaga님의 코드
int p[200000];
int n;

int find(int a) {
	if (p[a] == -1) return a;
	return p[a] = find(p[a]);
}

void merge(int a, int b) {
	a = find(a); b = find(b);
	if (a == b) return;
	if (a >= n) swap(a, b);
	p[b] = a;
}

int main() {
	memset(p, -1, sizeof(p));
	int m;
	scanf("%d %d", &n, &m);

	char c;
	int a, b;
	while (m--) {
		scanf(" %c %d %d", &c, &a, &b);
		a--; b--;
		if (a > b) swap(a, b);

		if (c == 'S') {
			merge(a, b);
			merge(a + n, b + n);
		}
		else {
			merge(a, b + n);
			merge(b, a + n);
		}
	}
	
	int cnt = 0;
	for (int i = 0; i < n; i++)
		if (find(i) == find(i + n))
			return !printf("0");

	for (int i = 0; i < n; i++)
		merge(i, i + n);

	printf("1");
	for (int i = 0; i < n; i++)
		if(i == find(i)) printf("0");
}

 

2-sat 느낌으로 푸신 것 같다.

 

s a b   :  a <-> b,  ~a <-> ~b

d a b  :  a <-> ~b, ~a <-> b

 

질의마다 위와같이 정점을 유지해 준 후, 모순이 있는지 확인한다.

u <-> ~u 인 경우 모순

 

이제 덩어리들의 개수만큼 0을 출력해주면 되는데, 출력해주기 전에 u와 ~u를 이어줘야 한다.

 

예를들어 p->~q와 ~p->q는 중복해서 세면 안되기 때문. (같은 의미를 갖는 구조지만 이어져있지 않으므로 덩어리의 수를 세주기 전에 이어줘야 한다.)