[BOJ / SCC] 4196 도미노

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

4196번: 도미노

 

4196 도미노

알고리즘 : 강한연결요소(SCC)

SCC를 이용하여 사이클을 하나의 정점으로 만들어 위상정렬의 방식을 일부 따와서 푸는 문제입니다.  위상정렬은 사이클이 존재하면 풀리지 않으므로 SCC를 이용하여 사이클을 제거해주고 새로운 SCC에서 indegree가 0인 것을 카운팅 해주면 풀이됩니다.

 

 

 

< CODE >

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX 100005

int cnt = 0, cNum[MAX], result;
bool chk[MAX];
int isDomino[MAX];
vector<int> adj[MAX];
int SCC;
int sccInd[MAX];
stack<int> s;

int n, m;

void init()
{
	cnt = 0;
	result = 0;
	SCC = 0;

	for (int i = 0; i < MAX; i++)
	{
		chk[i] = false;
		isDomino[i] = -1;
		cNum[i] = 0;
		adj[i].clear();
		sccInd[i] = 0;
	}
}

int dfs(int cur)
{
	cNum[cur] = ++cnt;
	s.push(cur);

	int p = cNum[cur];

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

		if (!cNum[to])
			p = min(p, dfs(to));
		else if (!chk[to])
			p = min(p, cNum[to]);
	}

	if (p == cNum[cur])
	{
		while (true)
		{
			int t = s.top(); s.pop();
			isDomino[t] = SCC + 1;
			chk[t] = true;

			if (t == cur)
				break;
		}

		SCC++;
	}

	return p;
}

void solve()
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < adj[i].size(); j++)
		{
			int to = adj[i][j];

			if (isDomino[i] != isDomino[to])
				sccInd[isDomino[to]]++;
		}
	}

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

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

	int tests; 

	cin >> tests;

	while (tests--)
	{
		init();

		cin >> n >> m;

		for (int i = 0; i < m; i++)
		{
			int f, t;

			cin >> f >> t;

			adj[f].push_back(t);
		}

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

		solve();

		cout << result << '\n';
	}

	return 0;
}

시간 : 160ms

 

태그 : #BOJ 도미노 #4196 도미노 #백준 도미노 #도미노 풀이 #SCC #강한연결요소