[BOJ] 2252 줄 세우기 [리스트, 큐, 이중 벡터 구현]

문제: https://www.acmicpc.net/problem/2252

 

 

문제 풀이:

위상정렬 알고리즘을 이용한다.

예제가 다음과 같을 때,

 

1->3   (indegree[3]++)

2->3   (indegree[3]++) 으로 보고

 

indegree가 0인 것들을 큐에 넣는다. 

앞에서부터 하나씩 빼면서 그 노드가 가리키는 노드의 indegree를 감소시켜 0이 되면 큐에 넣어준다.

 

 

소스 코드:

 

stl 사용

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

int n, m,indegree[32002];
vector<vector<int>> v;
queue<int> q;


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

	cin >> n >> m;
	v.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		indegree[b]++;
	}
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) q.push(i);
	}
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (auto i : v[cur]) {
			if (--indegree[i] == 0) q.push(i);
		}
	}
	return 0;
}

 

stl 미사용

#include <iostream>
using namespace std;

int n, m, q[32002], indegree[32002];
int v_pos, q_f, q_top = -1;
//bool v[32002][32002];

struct Node {
	int val;
	Node* next;
	Node(int n) {
		val = n;
		next = NULL;
	}
};

struct List {
	Node* head;
	Node* tail;
	List() {
		head = NULL;
		tail = NULL;
	}
	void insert(int n) {
		if (head == NULL) {
			head = new Node(n);
			tail = head;
			return;
		}
		tail->next = new Node(n);
		tail = tail->next;
	}
};
List v[32002];

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v[a].insert(b);
		indegree[b]++;
	}
	for (int i = 1; i <= n; i++) {
		if (indegree[i] == 0) q[++q_top] = i;
	}
	while (q_top - q_f >= 0) {
		int cur = q[q_f++];
		cout << cur << " ";

		Node* tmp = v[cur].head;
		while (tmp != NULL) {
			if (--indegree[tmp->val] == 0) q[++q_top] = tmp->val;
			tmp = tmp->next;
		}
	}
	return 0;
}