[6543번] The Bottom of a Graph

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. SCC :: http://www.crocus.co.kr/950

이 문제는 진출차수(Outdegree)를 찾는 문제이다.

진출차수가 무엇을 의미하냐면 

이 그림에서 1-3이 하나의 SCC이고 2가 또다른 SCC인데 2->3의 간선은 서로 다른 SCC속에 있으며 정점 2에서 정점 3으로 가는 간선이 있을 때 2의 진출 차수는 1개이고 3의 진입 차수는 1개라고 한다.

결국 답은 진출 차수가 없는 노드를 출력하면 되는것이므로 1,3이 되고 아래 그래프는 정점 1이 진출차수가 1이므로 답은 2가 된다.

그 외에 내용은 SCC를 이용하여 SCC로 묶어내고 진출 차수를 구하여 정답을 도출하면 된다. 

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <memory.h>
 
using namespace std;
 
const int MAX = 5002;
 
vector<int> adj[MAX];
stack<int> s;
 
bool finish[MAX]; // SCC 분리가 완료된 정점 = true
int dfsn[MAX]; // 각 노드 dfs 번호
int SCCnum[MAX]; // SCC의 인덱스 번호
int cnt; // dfs 번호
int SCCtotal; // SCC 총 개수
 
int dfs(int cur)
{
    dfsn[cur] = ++cnt;
 
    s.push(cur);
 
    int result = dfsn[cur];
 
    int len = adj[cur].size();
 
    for (int i = 0; i < len; i++)
    {
        int next = adj[cur][i];
 
        if (!dfsn[next])
            result = min(result, dfs(next));
 
        else if (!finish[next])
            result = min(result, dfsn[next]);
    }
 
    if (result == dfsn[cur])
    {
        while (1)
        {
            int t = s.top();
            s.pop();
            finish[t] = true;
            SCCnum[t] = SCCtotal;
 
            if (t == cur)
                break;
        }
 
        SCCtotal++;
    }
 
    return result;
}
 
int main()
{
    while (1)
    {
        int V, E;
        scanf("%d", &V);
 
        if (!V)
            break;
 
        scanf("%d", &E);
 
        for (int i = 0; i < MAX; i++)
            adj[i].clear();
 
        memset(finish, false, sizeof(finish));
        memset(dfsn, 0, sizeof(dfsn));
        memset(SCCnum, 0, sizeof(SCCnum));
        cnt = 0;
        SCCtotal = 0;
 
        for (int i = 0; i < E; i++)
        {
            int from, to;
            scanf("%d %d", &from, &to);
            adj[from].push_back(to);
        }
 
        for (int i = 1; i <= V; i++)
            if (!dfsn[i])
                dfs(i);
 
        int outdegree[MAX] = { 0 };
        for (int i = 1; i <= V; i++)
            for (int j : adj[i])
                if (SCCnum[i] != SCCnum[j])
                    outdegree[SCCnum[i]]++;
 
        vector<int> ans;
        for (int i = 1; i <= V; i++)
            if (outdegree[SCCnum[i]] == 0)
                printf("%d ", i);
 
        printf("\n");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>