[0x1A] 위상 정렬

방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬

하나의 그래프에서 여러개의 위상 정렬 결과가 나올 수 있다.

DAG 에서만 사용할 수 있다.

 

구현의 편의를 위한 성질

 

1. 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree값만 1 감소시켜도 과정을 수행 가능
2. indegree가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가

 

구현 방법

 

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다
2. indegree가 0인 정점들을 모두 큐에 넣는다
3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가한다
4. 해당 정점으로부터 연결된 모든 정점의 indegree값을 1 감소시킨다. 이 때, indegree가 0이 되었다면 그 정점을 큐에 추가한다
5. 큐가 빌 때 까지 3, 4번을 반복한다

 

vector<int> adj[10];
int deg[10];
int n;

queue <int> q;
vector<int> result;
for (int i = 1; i <= n; ++i)
{
    if (deg[i] == 0) q.push(i);
}
while (!q.empty())
{
    int cur = q.front(); q.pop();
    result.push_back(cur);
    for (int nxt : adj[cur])
    {
        deg[nxt]--;
        if (deg[nxt] == 0) q.push(nxt);
    }
}
if (result.size() != n)
    cout << "cycle exists";
else
{
    for (auto& x : result) cout << x << ' ';
}

 

연습 문제

 

2252: 줄 세우기

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[32001];
queue<int> q;
vector<int> ans;
int ind[32001];
int n, m;

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

	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		ind[b]++;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (!ind[i]) q.push(i);
	}

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		ans.push_back(cur);
		for (auto& nxt : adj[cur])
		{
			ind[nxt]--;
			if (!ind[nxt]) q.push(nxt);
		}
	}

	for (auto& i : ans) cout << i << ' ';

	return 0;
}

 

따로 ans에 결과를 저장하여 출력할 필요 없이 q의 루프 내에서 바로 출력해주면 된다

 

기본 문제

 

2623: 음악프로그램

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1001];
vector<int> ans;
queue<int> q;
int ind[1001];
int n, m;

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

	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int k;
		queue<int> tq;
		cin >> k;
		while (k--)
		{
			int a;
			cin >> a;
			tq.push(a);
		}
		int t = tq.front(); tq.pop();
		while (!tq.empty())
		{
			int nxt = tq.front(); tq.pop();
			adj[t].push_back(nxt);
			ind[nxt]++;
			t = nxt;
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		if (!ind[i]) q.push(i);
	}

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		ans.push_back(cur);
		for (auto& nxt : adj[cur])
		{
			ind[nxt]--;
			if (!ind[nxt]) q.push(nxt);
		}
	}

	if (ans.size() != n)
		cout << 0;
	else
	{
		for (auto& i : ans) cout << i << '\n';
	}

	return 0;
}

 

21276: 계보 복원가 호석

#include <bits/stdc++.h>
using namespace std;

int n, m;
map<string, int> h;
vector<int> adj[1001];
vector<string> sv;
vector<string> ans[1001];
int ind[1001];

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

	cin >> n;
	sv.push_back("");
	for (int i = 1; i <= n; ++i)
	{
		string s;
		cin >> s;
		sv.push_back(s);
	}
	sort(sv.begin()+1, sv.end());
	for(int i = 1; i <= n; ++i) h.insert({sv[i], i});

	cin >> m;
	while (m--)
	{
		string s1, s2;
		cin >> s1 >> s2;
		adj[h[s2]].push_back(h[s1]);
		ind[h[s1]]++;
	}

	vector<string> t;
	queue<int> q;
	for (int i = 1; i <= n; ++i)
	{
		if (!ind[i])
		{
			q.push(i);
			t.push_back(sv[i]);
		}
	}
	sort(t.begin(), t.end());
	cout << t.size() << '\n';
	for (auto& i : t) cout << i << ' ';
	cout << '\n';

	while (!q.empty())
	{
		int cur = q.front(); q.pop();
		for (auto& nxt : adj[cur])
		{
			ind[nxt]--;
			if (!ind[nxt])
			{
				q.push(nxt);
				ans[cur].push_back(sv[nxt]);
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		cout << sv[i] << ' ' << ans[i].size() << ' ';
		if (ans[i].size() > 0)
		{
			t.clear();
			for (auto& k : ans[i]) t.push_back(k);
			sort(t.begin(), t.end());
			for (auto& k : t) cout << k << ' ';
		}
		cout << '\n';
	}

	return 0;
}

 

그래프를 그려보면 진출차수가 0인게 루트가 되지만 그래프 방향을 반대로 바꾸어서 진입차수를 비교하는걸로 바꿈

사전순 출력이 필요해서 컨테이너들이 추가로 여러개 쓰임

단순히 자식의 숫자만 출력하면 최초 진입차수가 2 이상인 자식들까지 포함되기 때문에 진입차수가 1인 자식들만 따로 ans에 추가해서 출력해준다