[백준/BOJ] 백준 4196번 : 도미노

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

4196번: 도미노

타잔 알고리즘을 이용해 SCC를 구하고, SCC사이의 그래프를 만들어서 그 SCC사이의 그래프의 indegree가 0인 것의 개수를 구하는 방법을 통해 문제를 해결했다.

 

코드

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

int tc;
int n, m;
vector<int> adj[100001];
vector<int> visited(100001);
vector<int> maked(100001);
vector<int> node_id(100001);
vector<int> node_scc_id(100001);
int node_id_cnt = 0;
stack<int> st;
int scc_id_cnt = 0;
vector<int> scc_adj[100001];
vector<int> scc_indegree(100001);

void Pre()
{
	for (int i = 0; i < 100001; i++)
	{
		adj[i].clear();
		visited[i] = 0;
		maked[i] = 0;
		node_id[i] = 0;
		node_scc_id[i] = 0;
		scc_adj[i].clear();
		scc_indegree[i] = 0;
	}

	node_id_cnt = 0;
	scc_id_cnt = 0;
}

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

	node_id_cnt++;
	node_id[here] = node_id_cnt;

	int parent = node_id[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_id_cnt++;

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

			maked[st_top] = 1;
			node_scc_id[st_top] = scc_id_cnt;

			if (st_top == here)
				break;
		}
	}

	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 x, y;
			cin >> x >> y;

			adj[x].push_back(y);
		}

		for (int i = 1; i <= n; i++)
		{
			if (visited[i] == 0)
				Dfs(i);
		}

		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < adj[i].size(); j++)
			{
				int here = i;
				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_indegree[node_scc_id[there]]++;
				}
			}
		}

		int result = 0;
		for (int i = 1; i <= scc_id_cnt; i++)
		{
			if (scc_indegree[i] == 0)
				result++;
		}

		cout << result << "\n";
	}

	return 0;
}