BOJ 1765 - The Gangs

* BOJ 1765 - The Gangs (닭싸움 팀 정하기, https://www.acmicpc.net/problem/1765)

  [ 분류 - BFS, DFS/ DSU/ Hashing ]

  이분 그래프가 여러개 생길 수 있는 구조를 생각하자. 조건에 따르면 특정 Component A에 대해 A의 적은 단 하나 밖에 존재하지 않는다.

  따라서 자신의 적을 저장할 자료구조(Hashing)와 친구를 저장할 자료구조(인접 행렬 및 리스트/ DSU)를 정해야 한다. 

* 풀이

  친구를 저장할 때는 인접 행렬 및 리스트로 저장하는 것은 꽤 간단하다. 하지만 적을 저장할 때는 어떻게 해야 할까?

  이분 그래프이기 때문에 적을 단 하나만 저장한다. 이를 루트로 두고, 들어오는 데이터에 따라 자신의 적을 읽어들여, 적과 적을 이어주도록 한다. 우리의 적은 "현재 저장된 적"과는 친구이기 때문에 마찬가지로 인접 행렬 및 리스트에 연결을 시켜줘야만 한다. 이렇게하면 문제에서 주어진 조건대로 Components를 나눌 수 있다.

- 코드

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_V = 1001;
vector<int> fadj[MAX_V];
int vi[MAX_V], adjFoe[MAX_V]; //first of enemy

void bfs(int s) {
	int u;
	queue<int> q;
	q.push(s);
	vi[s] = 1;
	while (!q.empty()) {
		u = q.front(), q.pop();
		for (int& v : fadj[u])
			if (!vi[v]) {
				vi[v] = 1;
				q.push(v);
			}
	}
}
int main() {
	char r;
	int n, m, u, v, i, ans = 0;
	memset(adjFoe, -1, sizeof adjFoe);
	scanf("%d%d\n", &n, &m);
	while (m--) {
		scanf("%c%d%d\n", &r, &u, &v);
		u--, v--;
		if (r == 'F') {
			fadj[u].push_back(v);
			fadj[v].push_back(u);
		}
		else {
			if (adjFoe[u] == -1)
				adjFoe[u] = v;
			if (adjFoe[v] == -1)
				adjFoe[v] = u;

			fadj[adjFoe[u]].push_back(v);
			fadj[v].push_back(adjFoe[u]);

			fadj[adjFoe[v]].push_back(u);
			fadj[u].push_back(adjFoe[v]);
		}
	}

	for (i = 0; i<n; i++)
		if (!vi[i]) {
			bfs(i);
			ans++;
		}
	printf("%d", ans);

	return 0;
}