[백준/BOJ] 백준 3977번 : 축구 전술

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

3977번: 축구 전술

 

구역의 움직임을 그래프로 표현한 뒤 그래프를 SCC(강한 연결 요소)로 표현하여, SCC로 표현된 요소(Component)들 간의 그래프를 다시 만들고, SCC의 요소들 간의 그래프는 DAG라는 특징을 이용해 SCC 요소로 만든 그래프에서 indegree가 0인 요소가 1개만 존재하는지 확인하는 방법으로 모든 구역에 도달하는 시작 구역이 존재하는지 확인했다. 그리고 indegree가 0인 요소가 1개만 존재한다면, 해당 요소에 속한 구역들을 오름차순으로 출력하는 방식으로 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;

int tc;
int n, m;
vector<int> adj[100005];

vector<int> visited(100005);
int node_id_cnt;
vector<int> node_id(100005);
stack<int> st;

vector<int> scc_maked(100005);
int scc_id_cnt;
vector<int> node_scc_id(100005);
vector<int> scc_id_node[100005];
vector<int> scc_size(100005);

vector<int> scc_adj[100005];
vector<int> scc_adj_indegree(100005);

vector<int> result;

void Pre()
{
	node_id_cnt = 0;
	scc_id_cnt = 0;
	result.clear();

	for (int i = 0; i < 100005; i++) {
		adj[i].clear();
		visited[i] = 0;
		node_id[i] = 0;
		scc_maked[i] = 0;
		node_scc_id[i] = 0;
		scc_id_node[i].clear();
		scc_size[i] = 0;
		scc_adj[i].clear();
		scc_adj_indegree[i] = 0;
	}
}

int Dfs(int here)
{
	visited[here] = 1;

	node_id_cnt++;
	node_id[here] = node_id_cnt;

	int parent = node_id[here];
	st.push(here);

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];

		if (visited[there] == 0) {
			parent = min(parent, Dfs(there));
		}

		else if (scc_maked[there] == 0) {
			parent = min(parent, node_id[there]);
		}
	}

	if (parent == node_id[here]) {

		scc_id_cnt++;

		while (!st.empty()) {
			int st_top = st.top();
			st.pop();

			node_scc_id[st_top] = scc_id_cnt;
			scc_maked[st_top] = 1;
			scc_id_node[scc_id_cnt].push_back(st_top);

			if (st_top == here) {
				break;
			}
		}

		scc_size[scc_id_cnt] = scc_id_node[scc_id_cnt].size();
	}

	return parent;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> tc;

	for (int t = 0; t < tc; t++) {
		Pre();

		cin >> n >> m;

		for (int i = 0; i < m; i++) {
			int u, v;
			cin >> u >> v;

			adj[u].push_back(v);
		}

		//scc(강한 연결 요소)로 묶는다
		for (int i = 0; i < n; i++) {
			if (visited[i] == 0) {
				Dfs(i);
			}
		}

		//scc간의 그래프를 만든다
		for (int i = 0; i < n; i++) {
			int here = i;
			for (int j = 0; j < adj[i].size(); j++) {
				int there = adj[i][j];
				if (node_scc_id[here] != node_scc_id[there]) {
					scc_adj[node_scc_id[here]].push_back(node_scc_id[there]);
					scc_adj_indegree[node_scc_id[there]]++;
				}
			}
		}

		//scc의 그래프의 indegree가 0인개 1개만 존재하는지 확인한다
		int check = 0;
		int start_scc_id = -1;
		for (int i = 1; i <= scc_id_cnt; i++) {
			if (scc_adj_indegree[i] == 0) {
				check++;
				start_scc_id = i;

				if (check > 1) {
					break;
				}
			}
		}

		if (check != 1) {
			cout << "Confused" << "\n";
		}

		else {

			for (int i = 0; i < scc_id_node[start_scc_id].size(); i++) {
				int result_node = scc_id_node[start_scc_id][i];
				result.push_back(result_node);
			}

			sort(result.begin(), result.end());

			for (int i = 0; i < result.size(); i++) {
				cout << result[i] << "\n";
			}
		}

		cout << "\n";
	}

	return 0;
}