12877 - 먹이 사슬

step 1

이 문제를 쉽게 사람들이 가위바위보를 하는 것으로 생각하겠습니다. A와 B의 승패, B와 C의 승패를 알면 A와 C의 승패를 알 수 있습니다. 이제 승패를 아는 사람들끼리 하나의 그룹으로 묶는다고 생각하겠습니다.

처음에는 어떠한 승패도 모르니 전부 크기 1인 그룹에 들어가 있습니다.

어떤 두 사람이 다른 그룹이 들어가 있으면 절대 모순이 발생하지 않습니다. 승패에 상관없이 그 사람들이 포함된 그룹을 하나로 묶어줍니다.

 

만약 같은 그룹에 들어가 있으면 이제 계산을 해 줘야 합니다.

step 2

Union find를 이용해 그룹을 묶어줄 수 있습니다. 이때, 자신과 부모 사이의 승패도 같이 기록해 둡니다.

다음과 같은 상황을 생각해 봅시다. 1은 부모가 이긴 것, -1은 부모가 진 것, 0은 무승부입니다. 4가 3을 이겼다고 생각해 봅시다.

 

3과 1의 승패, 3과 4의 승패, 4와 5의 승패를 알고 있으니 5와 1의 승패도 알 수 있습니다. 이제 5가 1 밑으로 들어가면서 승패를 갱신해 주면 됩니다.

 

만약 둘이 같은 그룹에 있었다면 계산에 모순이 있는지만 체크해 주면 됩니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
using namespace std;
int p[60000],lv[60000],st[600000];
int calc(int p, int s) {
	if (s == 0) return p;
	if (s == 1) {
		p--;
		if (p == -1) p = 2;
	}
	if (s == -1) {
		p++;
		if (p == 3) p = 0;
	}
	return p;
}
int fight(int x, int y) {
	if (x == y) return 0;
	if (x == y + 1 || x == 0 && y == 2) return 1;
	return -1;
}
int main() {
	int i, n, q,cnt=0;
	scanf("%d%d", &n, &q);
	for (i = 1;i <= n;i++) p[i] = i;
	for (i = 1;i <= q;i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if (y <= 0 || z <= 0 || y > n || z > n) { cnt++; continue; }
		int yy = 0, zz = 0;
		if (x == 2) yy = 1;
		while (y != p[y]) {
			yy = calc(yy, st[y]);
			y = p[y];
		}
		while (z != p[z]) {
			zz = calc(zz, st[z]);
			z = p[z];
		}
		if (y == z) {
			if (yy != zz) cnt++;
			continue;
		}
		if (lv[y] < lv[z]) {
			p[y] = z;
			st[y] = fight(yy, zz);
		}
		else if (lv[y] > lv[z]) {
			p[z] = y;
			st[z] = fight(zz, yy);
		}
		else {
			p[z] = y;
			st[z] = fight(zz, yy);
			lv[y]++;
		}
	}
	printf("%d", cnt);
	return 0;
}