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

1. 문제설명

단방향 그래프 관계가 주어지고

그래프에서 간선의 방향을 수정했을 때

위상정렬을 수행하면 단 하나의 경우의 수만 나오는지 확인하는 문제다.

2. 접근방법[알고리즘]

우선 위상정렬을 수행하는데 확인해야 할 게 두가지 있다.

첫 번째는

단 하나의 경우의 수만 등장하는지 ==

확실한 순위를 찾을 수 있는지 확인해야한다.

이를 확인하려면 위상정렬을 하면서 큐의 size를 확인해야 한다.

만약 하나의 노드에서 여러 노드로 퍼질 수 있다면

큐의 사이즈가 2를 넘게 되고 이때는 위상정렬의 가짓 수가 여러개가 되어서 확실한 순위를 찾을 수 없다.

두번째는 

사이클이 존재하다면 IMPOSSIBLE을 출력해야한다.

사이클이 존재하면 위상정렬이 불가능하고,

그 경우에 위상정렬 과정에서 degree(차수) 가 0이 되지 않는 노드가 생기기 때문에

모든 노드를 탐색하지 못한다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

bool adj[501][501];
int degree[501];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {

        memset(adj, 0, sizeof(adj));
        memset(degree, 0, sizeof(degree));
        int n;
        cin >> n;

        vector<int> pre;
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            pre.push_back(tmp);
        }

		for (int i = 0; i < pre.size(); i++) {
            for (int j = i + 1; j < pre.size(); j++) {
                adj[pre[i]][pre[j]] = 1;
                degree[pre[j]]++;
            }
        }

        int m;
        cin >> m;


        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;

            if (adj[a][b] == 1) {
                adj[a][b] = 0;
                degree[b]--;
                adj[b][a] = 1;
                degree[a]++;
            }
            else {
                degree[a]--;
                adj[b][a] = 0;
                adj[a][b] = 1;
                degree[b]++;
            }
        }

        
        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
            }
        }

        vector<int> ans;

        bool cantKnow = false;

        while (!Q.empty()) {

            if (Q.size() >= 2) {
                cantKnow = true;
                break;
            }

            int x = Q.front(); Q.pop();
            ans.push_back(x);

            for (int i = 1; i <= n; i++) {
                if (adj[x][i] == 1) {
                    int nx = i;

                    if (--degree[nx] == 0) {
                        Q.push(nx);
                    }

                }
            }
        }

        if (cantKnow) {
            cout << "?\n";
            continue;
        }


        if (ans.size()!=n) {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        else {
			for (auto x : ans) {
				cout << x << ' ';
			}
			cout << '\n';
        }


    }
  
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int n , m;
vector<pair<int,int> > adj[101]; // Node, Cnt
int degree[101];
int need[101][101];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;

		adj[b].push_back({ a,c });
		degree[a] += c;

    }

    queue<int> Q;
    vector<int> basic;

    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(i);
            basic.push_back(i);
            need[i][i] = 1;
        }
    }

    while (!Q.empty()) {
        int x = Q.front(); Q.pop();

        for (auto i : adj[x]) {
            int nx = i.first;
            int cnt = i.second;

            for (auto b : basic) {
                need[nx][b] += need[x][b] * cnt;
            }
            degree[nx] -= cnt;

            if (degree[nx] == 0) {
                Q.push(nx);
            }
        }      
    }


    for (auto x : basic) {
        cout << x << ' ' << need[n][x] << '\n';
    }

    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1001];
vector<int> point[1001];
int degree[1001];
int val[1001];

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

    for (int T = 0; T < t; T++) {
        int k, m, p;
        cin >> k >> m >> p;
        memset(val, 0, sizeof(val));
        memset(degree, 0, sizeof(degree));
        for (int i = 0; i < 1001; i++) {
            adj[i].clear();
            point[i].clear();
        }


        for (int i = 0; i < p; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            degree[b]++;
        }

        queue<int> Q;
        for (int i = 1; i <= m; i++) {
            if (degree[i] == 0) {
                Q.push(i);
                val[i] = 1;
            }
        }

        int ans = 0;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();

            for (auto nx : adj[x]) {
                point[nx].push_back(val[x]);

                if (--degree[nx] == 0) {
                    Q.push(nx);

                    sort(point[nx].begin(), point[nx].end());

                    int val_nx = point[nx][point[nx].size() - 1];
                    if (point[nx].size() >= 2 && val_nx == point[nx][point[nx].size() - 2]) {
                	    val[nx] = val_nx + 1;
                   	}
                    else {
						val[nx] = val_nx;
                    }

                    ans = max(ans, val[nx]);
                }
            }
        }



        cout << k << ' ' << ans << '\n';
    }

    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int d[1001];
vector<int> adj[1001];
int degree[1001];
int res[1001];

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

    for (int T = 0; T < t; T++) {
        int n, k;
        cin >> n >> k;
        memset(degree, 0, sizeof(degree));
        memset(res, 0, sizeof(res));
        memset(d, 0, sizeof(d));
        for (int i = 0; i < 1001; i++) adj[i].clear();


        for (int i = 1; i <= n; i++) {
            cin >> d[i];
        }

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            degree[b]++;
        }
        int w;
        cin >> w;

        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
                res[i] = d[i];
            }
        }

        while (!Q.empty()) {
            int x = Q.front(); Q.pop();

            for (auto nx : adj[x]) {
                res[nx] = max(res[nx], res[x] + d[nx]);
                if (--degree[nx] == 0) {
                    Q.push(nx);
                }
            }

        }


        cout << res[w] << '\n';



    }


    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> adj[32001];
int degree[32001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        degree[b]++;
    }

    priority_queue<int> Q;

    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(-i);
        }
    }
    vector<int> ans;

    while (!Q.empty()) {
        int x = -Q.top();
        Q.pop();
        ans.push_back(x);

        for (auto nx : adj[x]) {
            if (--degree[nx] == 0) {
                Q.push(-nx);
            }
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    

    return 0;
}

우선순위 큐를 활용한 위상정렬 문제

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

#include <bits/stdc++.h>

using namespace std;

int n, m;
int degree[1001];
vector<int> adj[1001];
int cost[501];
int res[501];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        cost[i] = t;

        int a;
        while (1) {
            cin >> a;
            if (a == -1) break;
            adj[a].push_back(i);
            degree[i]++;
        }
    }
    

    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            res[i] = cost[i];
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto nx : adj[x]) {
			res[nx] = max(res[nx], res[x] + cost[nx]);
			if (--degree[nx] == 0) Q.push(nx);
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << res[i] << '\n';
    }


    return 0;
}

위상정렬 다이나믹프로그래밍 문제

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

위상정렬을 수행하는데 사이클이 존재하면

계속해서 degree가 0이 되지 않기 때문에

#include <bits/stdc++.h>

using namespace std;

int n, m;
int degree[1001];
vector<int> adj[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    // 그래프 만들기 
    for (int i = 0; i < m; i++) {
        int tmp;
        cin >> tmp;

		int pre = -1;
        for (int j = 0; j < tmp; j++) {
            int now;
            cin >> now;
            if (pre != -1) {
                adj[pre].push_back(now);
                degree[now]++;
            }
            pre = now;
        }
    }

    vector<int> order;
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        order.push_back(x);


        for (auto nx : adj[x]) {
            if (degree[nx] > 0) {
				degree[nx]--;
                if (degree[nx] == 0) {
                    Q.push(nx);
                }
            }
        }
    }

    if (order.size() == n) {
        for (auto x : order) {
            cout << x << '\n';
        }
    }
    else {
        cout << 0 << '\n';
    }




    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int n, m;

int arr[1001][1001];
vector<pair<int, int> > wall;
bool ch[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int num[1001][1001];
int marked[1001*1001]; // cnt[mark] = 개수 


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    for (int i = 0; i < n; i++) {

        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            arr[i][j] = s[j]-'0';
            if (arr[i][j]) wall.push_back({ i,j });
        }
    }

    int mark = 1;
	queue<pair<int, int> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            
            if (arr[i][j] == 0 && num[i][j] == 0) {
				int cnt = 1;
                Q.push({ i,j });
                num[i][j] = mark;
                while (!Q.empty()) {
                    int x = Q.front().first;
                    int y = Q.front().second;
                    Q.pop();

                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];

                        if (nx < 0 || nx >= n || ny < 0 || ny >= m || num[nx][ny] || arr[nx][ny]) continue;
                        Q.push({ nx,ny });
                        cnt++;
                        num[nx][ny] = mark;
                    }
                }
				marked[mark] = cnt;
				mark++;
            }
        }
    }

    for (int i = 0; i < wall.size(); i++) {
        int x = wall[i].first;
        int y = wall[i].second;

        int wall_cnt = 1;
        set<int> s;

        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] > 0) continue;
            s.insert(num[nx][ny]);
        }

        for (auto k : s) {
            wall_cnt += marked[k];
        }
        arr[x][y] = (wall_cnt % 10);
    }




    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << arr[i][j];
        }
        cout << '\n';
    }
    return 0;
}