[basic] Topology Sort
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> topologySort(vector<vector<int>> &graph){
vector<int> answer;
vector<int> in_degree(graph.size(), 0);
int node;
for(int i=1; i<graph.size(); i++){
for(int j=0; j<graph[i].size(); j++) {
node = graph[i][j];
in_degree[node] += 1;
}
}
queue<int> q;
for(int i=1; i<graph.size(); i++){
if(in_degree[i] == 0){
q.push(i);
}
}
int cur_node;
for(int i=1; i<graph.size(); i++){
cur_node = q.front();
q.pop();
answer.push_back(cur_node);
for(int j=0; j<graph[cur_node].size(); j++){
node = graph[cur_node][j];
in_degree[node] -= 1;
if(in_degree[node] == 0){
q.push(node);
}
}
}
return answer;
}
void printSolution(vector<int> &v){
for(int i=0; i<v.size(); i++){
cout << v[i] << " ";
}
cout << endl;
}
int main(){
// adj list (1 ~ 7)
vector<vector<int> > graph1{
{},
{2, 5},
{3},
{4},
{6},
{6},
{7},
{},
};
vector<vector<int> > graph2{
{},
{2,3,4},
{5},
{5,6},
{},
{7},
{2},
{},
};
vector<int> answer = topologySort(graph1);
printSolution(answer);
answer = topologySort(graph2);
printSolution(answer);
return 0;
}
Author And Source
이 문제에 관하여([basic] Topology Sort), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@be-lgreen/basic-Topology-Sort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)