위상정렬 Feat DFS, BFS

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

2252번: 줄 세우기

이 문제가 Base 이다.

 

 

이하 BFS이다. 많이 써서 익숙하다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define pii pair<int, int>
using namespace std;
 
 
int node[32001] = { 0 };
vector<int> edge[32001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    int v, e;
    cin >> v >> e;
    int a, b;
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b;
        edge[a].push_back(b);
        node[b]++;
    }
 
 
    queue<int> q;
    for (int i = 1; i <= v; i++)
    {
        if (node[i] == 0)
            q.push(i);
    }
 
    // if q.empty() => Cycle
    while (!q.empty())
    {
        int t = q.front();
        cout << t << ' ';
        q.pop();
 
        for (int i = 0; i < edge[t].size(); i++)
        {
            int n = edge[t][i];
            node[n]--;
            if (node[n] == 0)
                q.push(n);
        }
    }
}
 
 

 

 

 

 

다음은 DFS이다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define pii pair<int, int>
using namespace std;
 
 
bool n_visit[32001] = {false};
//bool finish[32001] = {false} 싸이클 판별
int ans[32001];
int ac = 0;
vector<int> edge[32001];
 
void dfs(int node)
{
    n_visit[node] = true;
    for (int i = 0; i < edge[node].size(); i++)
    {
        if (n_visit[edge[node][i]] == false)
            dfs(edge[node][i]);
        //if(finish[edge[node][i] == false) 싸이클 판단의 중요 요소이다.
        // this is Cycle
    }
    ans[ac++] = node;
    //finish[node] = true;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int v, e;
    cin >> v >> e;
    int a, b;
    for (int i = 0; i < e; i++)
    {
        cin >> a >> b;
        edge[a].push_back(b);
    }
 
    for (int i = 1; i <= v; i++)
    {
        if (n_visit[i] == false)
            dfs(i);
    }
    for (int i = ac - 1; i >= 0; i--) // 뒤집어줘야 한다.
        cout << ans[i] << ' ';
}