[백준] 1765 닭싸움 팀 정하기

문제

닭싸움은 월드의 전통이다. 이번 캠프에서도 어김없이 닭싸움 대회가 열렸다. 그런데, 닭싸움을 하기 위해서는 반드시 누가 우리 편이고, 누가 우리 편이 아닌지를 알아야 할 것이다. 닭싸움의 팀을 정하는 원칙은, 평소 학생들의 인간관계에 따라 다음과 같이 정리할 수 있다.

1. 내 친구의 친구는 내 친구이다.
2. 내 원수의 원수도 내 친구이다.

이 때 두 학생이 친구이면 같은 팀에 속해있어야 하며, 같은 팀에 속해 있는 사람들끼리는 전부 친구여야 한다.

학생들의 인간관계가 주어지면, 닭싸움을 위한 팀 정하기를 할 때, 최대 얼마나 많은 팀이 만들어질 수 있는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 n이 주어진다. 각 학생들은 1부터 n까지 번호가 매겨져 있다. (2 ≤ n ≤ 1000) 

둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (1 ≤ m ≤ 5000)

다음 m개의 줄에는 한 줄에 한 개씩, 학생 간의 인간관계가 F p q 혹은 E p q의 형태로 공백으로 구분되어 주어진다. (1 ≤ p < q ≤ n)

첫 번째 글자가 F인 경우에는 p와 q가 친구인 것이고, E인 경우는 p와 q가 원수인 경우이다. 

입력은 모순이 없음이 보장된다. 즉, 두 학생이 동시에 친구이면서 원수인 경우는 없다.

 

두 학생이 친구면 반드시 같은 팀에 속해있어야합니다.

따라서 친구관계가 있으면 팀을 정할 수 있습니다.

 

원수의 원수는 친구입니다.

원수정보로 친구정보를 구할 수 있습니다.

한 친구에대해 n명이 모두 그 친구에대해 원수라면 그 n명은 모두 친구입니다.

따라서 원수정보로 나머지 친구정보를 모두 구한 후,

dfs를 사용해서 만들 수 있는 팀의 개수를 구할 수 있습니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

int N, M, f[1001][1001], cnt, v[1001];
vi enemy[1001];
char C;
void dfs(int k) {
	v[k] = cnt;
	REP(i, N) {
		if (i == k)continue;
		if (f[k][i] && !v[i])dfs(i);
	}
}
int main() {
	FAST;
	cin >> N >> M;
	while (M--) {
		int a, b;
		cin >> C >> a >> b;
		if (C == 'E') {
			enemy[a].push_back(b);
			enemy[b].push_back(a);
		}
		else if (C == 'F') {
			f[a][b] = 1;
			f[b][a] = 1;
		}
	}
	REP(i, N) {
		for (int r : enemy[i]) {
			for (int q : enemy[i]) {
				if (r == q)continue;
				f[r][q] = 1;
				f[q][r] = 1;
			}
		}
	}
	REP(i, N) {
		if (!v[i])cnt++, dfs(i);
	}
	cout << cnt;
}