[백준/BOJ] 백준 19649번 : 미담 전하기

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

19649번: 미담 전하기

강한 연결 요소(SCC)를 이용해 SCC를 만들고 SCC사이의 그래프를 만든 뒤, 위상 정렬을 통해 k가 속한 SCC까지 탐색하였다. 탐색과정에서 간접 미담 전파자를 최대로 만들 수 있는 경우를 찾고 경로를 만들었으며, 이동경로를 vector<int> come_from(10001, 0)을 통해 저장하여 최대 간접 미담 전파자 수와 이때의 직접 미담 전파자를 찾았다.

 

코드

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

int n, m;
vector<int> adj[10001];
int k;

vector<int> visited(10001, 0);
vector<int> node_id(10001, 0);
int id_cnt = 0;
stack<int> st;
vector<int> maked(10001, 0);
int scc_cnt = 0;
vector<int> node_scc(10001, 0);
vector<int> scc_size(10001, 0);
vector<int> scc_adj[10001];
vector<int> scc_indegree(10001, 0);
vector<int> cache(10001, 0);
vector<int> come_from(10001, 0);
int result1, result2;

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

	id_cnt++;
	node_id[here] = id_cnt;

	int parent = id_cnt;
	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 (maked[there] == 0)
		{
			parent = min(parent, node_id[there]);
		}
	}

	if (parent == node_id[here])
	{
		scc_cnt++;

		int this_scc_size = 0;

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

			this_scc_size++;

			node_scc[st_top] = scc_cnt; //해당 노드가 어떤 scc에 속하는지 저장
			maked[st_top] = 1;

			if (st_top == here)
				break;
		}

		scc_size[scc_cnt] = this_scc_size; //해당 scc의 크기(몇개의 노드가 있는지)저장
	}

	return parent;
}

int Find(int here)
{
	//here이 시작점일때
	if (come_from[here] == here)
		return here;

	return Find(come_from[here]);
}

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

	cin >> n >> m;

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

		cin >> u >> v;

		adj[u].push_back(v);
	}

	cin >> k;

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

	//scc끼리 그래프를 만든다
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < adj[i].size(); j++)
		{
			if (node_scc[i] != node_scc[adj[i][j]])
			{
				scc_adj[node_scc[i]].push_back(node_scc[adj[i][j]]);
				scc_indegree[node_scc[adj[i][j]]]++;
			}
		}
	}

	//scc그래프를 위상정렬을 이용해 탐색한다

	queue<int> q;
	for (int i = 1; i <= scc_cnt; i++)
	{
		if (scc_indegree[i] == 0)
		{
			cache[i] = scc_size[i];
			come_from[i] = i;
			q.push(i);
		}

	}

	while (!q.empty())
	{
		int here = q.front();
		q.pop();

		//위상 정렬을 통해 k가 위치한 scc에 도착 했을때
		if (here == node_scc[k])
			break;

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

			//here에서 there로 가는 경우가 there로 가는 길 중 더 많은 간접 미담 전파자를 만들 수 있을때
			if (cache[there] < cache[here] + scc_size[there])
			{
				come_from[there] = here;
				cache[there] = cache[here] + scc_size[there];
			}

			scc_indegree[there]--;

			if (scc_indegree[there] == 0)
				q.push(there);
		}
	}

	//가장 많은 간접 미담 전파자를 만드는 시작 지점의 scc를 이동 경로를 통해 찾는다
	int start_scc = Find(node_scc[k]);

	for (int i = 1; i <= n; i++)
	{
		if (node_scc[i] == start_scc && i != k)
		{
			result1 = i;
			break;
		}
	}

	result2 = cache[node_scc[k]];

	result2--; //직접 미담 전파자 뺴기

	if (scc_size[node_scc[k]] == 1) //미담 당사자가 간접 미담 전파자가 되지 않을때
		result2--;

	if (result2 == 0)
		cout << 0 << "\n";
	else
		cout << result1 << " " << result2 << "\n";

	return 0;
}