可达性

题目描述：

给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，
输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。

u1s1，这个题目描述讲的很难懂，你说是阅读理解都不为过，特别是最后一句，什么叫这些集合生序排序后字典序最小的？我一开始理解的是“输出这些集合升序排序后字典序最小的那个集合的元素”，但听雨巨的意思是，“将每个集合升序排序后，输出每个集合的第一个元素”，艹？

思路：

说简单点就是缩点，计算缩点后每个点集的入度，输出每个入度为0的点集中最小的点的序号

那为什么要看入度为0的呢？因为入度为0的点只能通向别的点，而不能由其他点到达，所以这些入度为0的点是可以到达除他们以外的所有的点，符合要求

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1.0E-8
#define endl '\n'
//#define inf 0x3f3f3f3f
#define MAX  300000 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, x, y, z;

int tot;//链式前向星建图
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int tim;//时间戳
int cnt;//缩点后点的数量
int maxn;
int color[MAX];//原来的点对应的新的点的编号
int in[MAX];//缩点后每个点的编号
int num[MAX];//缩点后每个点集包含的点数
stack<int>st;
int dfn[MAX], low[MAX];
bool vis[MAX];
void tarjan(int u){
    st.push(u);
    dfn[u] = low[u] = ++tim;
    vis[u] = 1;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])low[u] = min(low[u], dfn[v]);//这里别写错了，是判断vis[v]
    }
    if(dfn[u] == low[u]){
        int now;
        ++cnt;
        do {
            now = st.top();
            vis[now] = 0;
            st.pop();
            color[now] = cnt;
            ++num[cnt];
        } while (now != u);
        maxn = max(maxn, num[cnt]);
    }
}


int main(){
    sdd(n, m);
    for(int i = 1; i <= m; ++i){
        sdd(x, y);
        add(x, y);//建图
    }
    for(int i = 1; i <= n; ++i){
        if(!dfn[i])tarjan(i);
    }
    for(int i = 1; i <= n; ++i){//建新图
        for(int j = head[i]; j; j = tr[j].nex){
            int v = tr[j].to;
            if(color[i] != color[v]){
                ++in[color[v]];
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= cnt; ++i){
        if(!in[i])++ans;//计算有几个入度为0的点集
    }
    cout<<ans<<endl;
    mem(vis, 0);
    for(int i = 1; i <= n; ++i){
        if(!in[color[i]] && !vis[color[i]]){
            vis[color[i]] = 1;
            cout<<i<<' ';
        }
    }
    cout<<endl;
    return 0;
}