[SCC, 난이도 중상] 백준 9466번 텀 프로젝트

원래 알고리즘 분류상 DFS에 들어가 있던 문제인데, 강한 결합요소(SCC) 유형이라고 보는게 더 좋을 것 같아서 그래프 카테고리에 포스팅 한다. 강한 결합요소 알고리즘도 DFS를 쓴다.

 

강한 결합요소 알고리즘을 간단하게 설명하자면 이렇다.

일단 아래 그림은 9466번 예제에서 첫 번째 케이스를 도식화 한것이다. 3번은 자기 자신을 가리킨다는 의미로 동그라미로 감쌌다.

 

 

여기서 SCC는 5개다. (1번), (2번), (3번), (4번,6번,7번) , (5번)

여기서 (4번,6번,7번)은 사이클로 되어있으므로 하나의 SCC그룹이라고 하는 것이다.

아래 소스 코드에서 dfs함수가 SCC(강한결합요소) 알고리즘이다.

 

그런데 여기서 한가지 처리를 해줘야 한다.

서로 선택 받고 있는 그룹은 (3번),(4번,6번,7번) 그룹 2개이니 5개의 SCC중에서 저 2개의 SCC를 가려내야 한다는 것이다.

 

이 방법은 간단하다.

다음 2가지 조건중 하나라도 참이면 팀이 될 수 있다.

1. SCC그룹의 요소가 둘 이상이다.

2. SCC그룹의 요소가 하나이고, 그 하나의 요소가 자신을 가리키고 있다면 팀이 될 수 있다.

 

그리고 SCC그룹안에 속해있는 모든 노드(학생)들을 count 하면

[count = 팀을 이루고 있는 학생 수] 가 된다.

최종 답은 각 케이스마다 n-count 를 출력해주면 된다.

 

테스트케이스 문제이므로 모든 배열, 변수값은 초기화 해주자.

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
int id, d[100001];
vector<int> a[100001];
bool finished[100001];
vector<vector<int> > SCC;
stack<int> s;
int mini(int a, int b) {
	if (a < b) return a;
	else return b;
}
int dfs(int x) {
	d[x] = ++id;
	s.push(x);
	int parent = d[x];
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (d[y] == 0) parent = mini(parent, dfs(y));
		else if (!finished[y]) parent = mini(parent, d[y]);
	}
	if (parent == d[x]) {
		vector<int> scc;
		while (1) {
			int f = s.top();
			s.pop();
			scc.push_back(f);
			finished[f] = true;
			if (f == x) break;
		}
		if (scc.size() > 1) SCC.push_back(scc);
		else if (scc.size() == 1 && a[scc[0]][0] == scc[0]) {
			SCC.push_back(scc);
		}
	}
	return parent;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	for (int test = 0; test < t; test++) {
		int n;
		cin >> n;
		for (int i = 1; i < n + 1; i++) {
			int c;
			cin >> c;
			a[i].push_back(c);
		}
		for (int i = 1; i < n + 1; i++) {
			if (d[i] == 0) dfs(i);
		}
		int count = 0;
		for(int i=0;i<SCC.size();i++){
			count += SCC[i].size();
		}
		cout << n - count << "\n";
		memset(d, 0, sizeof(d));
		memset(finished, false, sizeof(finished));
		for (int i = 0; i < SCC.size(); i++) {
			SCC[i].clear();
		}
		SCC.clear();
		for (int i = 1; i < n + 1; i++) {
			a[i].clear();
		}
		id = 0;
	}
}