[백준 문제풀이] 백준 2623 c++

 

위상정렬을 통해 간단하게 구할 수 있다!

 

---

특정하게 따라야 하는 순서들 이외에는 정해진 조건이 없으므로, 여러 답이 나올 수 있다.

 

- 두 개의 큐를 통해서 구현

- 하나의 큐는 위상정렬을 구현할 때 사용

- 다른 하나는 값을 순서대로 저장하고 큐의 size 를 확인하여 가능한 순서가 존재하는지 유무를 파악할 수 있도록 사용

 

---

1 4 3 의 순서라면 node[1]에 4를 추가, node[4]에 3을 추가 하는 형식으로 구현

-> 1의 뒤에 모든 노드를 추가 할 필요가 없다!

 

#include <iostream>
#include <queue>
#include <vector>

int check[1001] = {};
std::vector<std::vector<int>> v;
std::queue<int> q;

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, m;
	std::cin >> n >> m;

	v.assign(n + 1, std::vector<int>(0));

	int a, b;
	int tmp[1001] = { };
	for (int i{ 0 }; i < m; i++) {
		std::cin >> a;
		for (int j{ 1 }; j <= a; j++) {
			std::cin >> tmp[j];
		}
		for (int j{ 1 }; j < a; j++) {
			v[tmp[j]].push_back(tmp[j + 1]);
			check[tmp[j + 1]]++;
		}
	}

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

	std::queue<int> ans;
	while (!q.empty()) {
		int k = q.front();
		q.pop();
		ans.push(k);
		for (int i{ 0 }; i < v[k].size(); i++) {
			int j = v[k][i];
			check[j]--;
			if (!check[j]) {
				q.push(j);
			}
		}
	}

	if (ans.size() < n) {
		std::cout << "0\n";
	}
	else {
		while (!ans.empty()) {
			std::cout << ans.front() << "\n";
			ans.pop();
		}
	}
}