链接：

来源：牛客网

题目描述

给出一个 0 ≤ N ≤ 10

⁵ 点数、0 ≤ M ≤ 10

⁵ 边数的有向图，

输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。

输入描述:

第一行为两个整数 1 ≤ n, m ≤ 10

⁵

， 接下来 M 行，每行两个整数 1 ≤ u, v ≤ 10

⁵

表示从点 u 至点 v 有一条有向边。 数据保证没有重边、自环。

输出描述:

第一行输出一个整数 z，表示作为答案的点集的大小； 第二行输出 z 个整数，升序排序，表示作为答案的点集。

示例1

输入

7 104 55 12 56 57 24 21 25 33 53 6

输出

24 7 题意 ： 寻找最小的点集，使得从这些点出发的可以遍历整张图 思路分析 ： Trajin + 缩点 代码示例 ：

const int maxn = 1e5+10;vector
          
           ve[maxn];vector
           
            id[maxn]; // 强连通的编号int n, m;int dfn[maxn], low[maxn]; // 每个点在这棵树中，最小的子树的根int tot = 0, key = 0;int Stack[maxn], belong[maxn]; // 缩点bool instack[maxn];int scc; // 强连通分量的个数void tarjin(int x){    low[x] = dfn[x] = ++key; // 注意是 ++在前，因为下面下面深搜的判断是为0表示没访问过的点，才去搜    Stack[tot++] = x;    instack[x] = true;    for(int i = 0; i < ve[x].size(); i++){        int to = ve[x][i];                if (!dfn[to]) {            tarjin(to);            low[x] = min(low[x], low[to]);        }        else if (instack[to]){            low[x] = min(low[x], dfn[to]);        }    }     if (low[x] == dfn[x]){        scc++;        int v;        do{            v = Stack[--tot];            instack[v] = false;            belong[v] = scc;            id[scc].push_back(v);        }        while(v != x);     }  }int u[maxn], v[maxn], in[maxn];vector
            
             ans;void solve(){    }int main() {    //freopen("in.txt", "r", stdin);    //freopen("out.txt", "w", stdout);    cin >> n >> m;    int a, b;        memset(dfn, 0, sizeof(dfn));    memset(low, 0, sizeof(low));    memset(instack, false, sizeof(instack));    memset(in, 0, sizeof(in));    for(int i = 1; i <= m; i++){        scanf("%d%d", &u[i], &v[i]);        ve[u[i]].push_back(v[i]);    }    for(int i = 1; i <= n; i++){        if (!dfn[i]) tarjin(i);    }       //for(int i = 1; i <= n; i++) printf("%d ", belong[i]);        for(int i = 1; i <= m; i++){        if (belong[u[i]] == belong[v[i]]) continue;        in[belong[v[i]]]++;    }    for(int i = 1; i <= scc; i++) sort(id[i].begin(), id[i].end());    for(int i = 1; i <= scc; i++){        if (!in[i]) {            ans.push_back(id[i][0]);        }    }    sort(ans.begin(), ans.end());    printf("%d\n", ans.size());    for(int i = 0; i < ans.size(); i++){        printf("%d%c", ans[i], i==ans.size()-1?'\n':' ');    }    return 0;}