위상정렬

 

[설명]

m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

 

 

 

[순서]

 

 

 

 

[예제]

- 큐를 이용한 위상 정렬 :

www.acmicpc.net/problem/2252

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int M = 1000 + 5;

vector<int> v[M];
int line[M];
int res[M];

int main() {
	//input
	int n, m;
	cin >> n >> m;

	while (m--) {
		int num;
		cin >> num;

		int a;
		cin >> a;
		for (int i = 0; i < num - 1; ++i) {
			int b;
			cin >> b;

			line[b]++;

			v[a].push_back(b);
			a = b;
		}
	}

	//sol
	queue<int> q;
	for (int i = 1; i <= n; ++i) {
		if (line[i] == 0) {
			q.push(i);
		}
	}
	for (int i = 0; i < n; ++i) {
		//종료조건
		if (q.empty()) {
			cout << 0 << endl;
			return 0;
		}

		//진행조건
		int now = q.front();
		q.pop();

		res[i] = now;
		for (int j = 0; j < v[now].size(); ++j) {
			int next = v[now][j];

			line[next]--;

			if (line[next] == 0) {
				q.push(next);
			}
		}
	}

	//ouput
	for (int i = 0; i < n; ++i) {
		cout << res[i] << "\n";
	}
}

www.acmicpc.net/problem/2623

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int M = 32000 + 5;

vector<int> v[M];
int line[M];
int res[M];

int main() {
	//input
	int n, m;
	cin >> n >> m;

	while (m--) {
		int a, b;
		cin >> a >> b;
		
		line[b]++;
		v[a].push_back(b);
	}

	//sol
	priority_queue<int, vector<int> , greater<int>> q;
	for (int i = 1; i <= n; ++i) {
		if (line[i] == 0) {
			q.push(i);
		}
	}
	for (int i = 0; i < n; ++i) {

		//진행조건
		int now = q.top();
		q.pop();

		res[i] = now;
		for (int j = 0; j < v[now].size(); ++j) {
			int next = v[now][j];

			line[next]--;

			if (line[next] == 0) {
				q.push(next);
			}
		}
	}

	//ouput
	for (int i = 0; i < n; ++i) {
		cout << res[i] << "\n";
	}
}

---

- 우선순위 큐를 이용한 위상정렬 :

www.acmicpc.net/problem/1766

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int M = 32000 + 5;

vector<int> v[M];
int line[M];
int res[M];

int main() {
	//input
	int n, m;
	cin >> n >> m;

	while (m--) {
		int a, b;
		cin >> a >> b;
		
		line[b]++;
		v[a].push_back(b);
	}

	//sol
	priority_queue<int, vector<int> , greater<int>> q;
	for (int i = 1; i <= n; ++i) {
		if (line[i] == 0) {
			q.push(i);
		}
	}
	for (int i = 0; i < n; ++i) {

		//진행조건
		int now = q.top();
		q.pop();

		res[i] = now;
		for (int j = 0; j < v[now].size(); ++j) {
			int next = v[now][j];

			line[next]--;

			if (line[next] == 0) {
				q.push(next);
			}
		}
	}

	//ouput
	for (int i = 0; i < n; ++i) {
		cout << res[i] << "\n";
	}
}

---

- 여러 위상 순서 중 가장 짧게 걸리는 위상 정렬 방법 구하기 :

www.acmicpc.net/problem/2056

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int M = 10000 + 5;

vector<int> v[M];
int time[M];
int res[M];

int main() {
	//input
	int n;
	cin >> n;
	
	for(int i = 1; i<=n; ++i){
		int t, m;
		cin >> t >> m; //5, 0 //1, 1

		res[i] = t;
		time[i] = t;//time[1] = 5; //time[2] = 1;
		
		if (m == 0) res[i] = t;
		else {
			while (m--) {
				int a;
				cin >> a;//1
				v[i].push_back(a);//v[2] : 1 //v[3] : 2 //v[4] : 1
			}

			int maxx = -1;
			for (int j = 0; j < v[i].size(); ++j) {
				//핵심코드
				if (maxx < res[v[i][j]]) {
					maxx = res[v[i][j]];
				}
			}res[i] += maxx;// res[2] = 6; //res[3] = 9;
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, res[i]);
	}

	cout << ans << endl;
}

www.acmicpc.net/problem/1516

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

int N;
int cost[501];
int ans[501];
int indegree[501];
vector<int> vec[501];

void bfs() {
	queue<int> q;
	for (int n = 1; n <= N; n++) {
		if (indegree[n] == 0) {
			q.push(n);
			ans[n] = cost[n];
		}
	}

	while (!q.empty()) {
		int nedge = q.front();
		q.pop();
		for (int m = 0; m < vec[nedge].size(); m++) {
			int e = vec[nedge][m];
			ans[e] = max(ans[e], ans[nedge] + cost[e]);
			if (--indegree[e] == 0)
				q.push(e);
		}
	}
}

int main() {
	cin >> N;
	for (int n = 1; n <= N; n++) {
		int edge;
		cin >> cost[n];
		while (cin >> edge, edge != -1) {
			vec[edge].push_back(n);
			indegree[n]++;    //진입차수
		}
	}

	//for (int n = 1; n <= N; n++) {
	//	cout << indegree[n] << endl;
	//}
	
	bfs();
	for (int n = 1; n <= N; n++) {
		cout << ans[n] << endl;
	}
}