题目分析

这道题目要求我们找到有向图中的所有汇点（sink nodes）。汇点的定义是：对于图中所有从该点可达的节点，该点也必须可以从这些节点可达。换句话说，汇点所在的强连通分量（SCC）不能有出边指向其他强连通分量。

方法思路

1. 强连通分量（SCC）检测：使用 Tarjan 算法找到图中的所有强连通分量。Tarjan 算法通过深度优先搜索（DFS）遍历图，标记每个节点的发现时间和最低可达祖先，从而识别 SCC。
2. 计算出度：对于每个 SCC，计算其出度（即指向其他 SCC 的边数）。如果一个 SCC 的出度为 0，则该 SCC 中的所有节点都是汇点。
3. 输出结果：将所有出度为 0 的 SCC 中的节点按升序输出。

解决代码

#include <iostream>
#include <cstring>
#include <algorithm> 
#include <stack>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 100005;

int cnt = 0;
struct Snode {
    int to;
    int next;
}edge[maxn];
int head[maxn];

// tarjan
int num = 0;
int dfn[maxn], low[maxn];
bool ins[maxn];
stack<int> s;
int scc;
int belong[maxn];
int outDeg[maxn];

void add(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void print(int n)
{
    for (int j = 1; j <= n; j++)
    {
        cout << j << "-";
        for (int i = head[j]; ~i; i = edge[i].next)
        {
            cout << edge[i].to;
        }
        cout << endl;
    }
}

void init(){
    num = 0;
    cnt = 0;
    scc = 0;
    memset(head, -1, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(belong, -1, sizeof(belong));
    memset(outDeg, 0, sizeof(outDeg));
}

void tarjan(int u) {
    dfn[u] = low[u] = ++num;
    ins[u] = true;
    s.push(u);
    for(int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    // SCC
    if(low[u] == dfn[u]) {
        int v;
        do{
            v = s.top();
            s.pop();
            // cout << v << " ";
            belong[v] = scc;
            ins[v] = false;
        }while(v != u);
        scc++;
        // cout << endl;
    }
}

int main() {
    int n, e;
    while(cin >> n){
        if(!n){
            break;
        }
        init();
        cin >> e;
        for (int i = 0; i < e; i++)
        {
            int u, v;
            cin >> u >> v;
            add(u, v);
        }
        // print(n);
        for (int i = 1; i <= n; i++)
        {
            if (!dfn[i])
            {
                tarjan(i);
            }
        }
        for (int u = 1; u <= n; u++)
        {
            for (int i = head[u]; ~i; i = edge[i].next)
            {
                int v = edge[i].to;
                if (belong[u] != belong[v])
                {
                    outDeg[belong[u]]++;
                }
            }
        }
        int flg = 0;
        for (int u = 1; u <= n; u++)
        {
            if (!outDeg[belong[u]])
            {
                if (flg)
                {
                    cout << " ";
                }
                else
                {
                    flg = 1;
                }
                cout << u;
            }
        }
        cout << endl;
    }

    return 0;
}