可达性_牛客博客

@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，
输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。输入描述:
第一行为两个整数 1 ≤ n, m ≤ 105，接下来 M 行，每行两个整数 1 ≤ u, v ≤ 105 表示从点 u 至点 v
有一条有向边。数据保证没有重边、自环。

输出描述:

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

示例1
输入

输出

2
4 7

题解：

很显然用tarjan来做
我们先进行缩点
因为边是有向边，我们可以记录搜点后每个点的入度与出度情况（其实光记录入度就可以）
我们要找从这些点出发可以找到其他点，那我们是不是必须带上那些没有入度的点，因为这些点连入度都没有，其他点根本不可能指向它，只能是我们主动从这些点出发。
如果一个点有入点，那么我们无需找他，找他的上家（也就是指向它的点），即可，这样向上找最后得到的也是入度为0的点
最后输出时要排序

代码：

代码有详细的注释

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct node
{
    int v, next;
}edge[maxn];
vector<int>p;
stack <int> s;
int dfn[maxn],low[maxn];
int color[maxn],in[maxn];
int tot,block;
int head[maxn],pre[maxn];
int n,m,cnt,C,X;
bool vis[maxn];
void add(int from, int to) {
    edge[++cnt].v=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
}
void tarjan(int u) {
    dfn[u]=low[u]= ++tot;
    vis[u]=1;
    s.push(u);
    for(int i=head[u];i!=-1;i=edge[i].next) 
    {
        int v=edge[i].v;
        if (!dfn[v]) 
        {
            tarjan(v);
            low[u]= min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        block++;
        int v;
        do {
            v=s.top();
            s.pop();
            color[v]=block;
            pre[block]=min(v, pre[block]);//pre保存的是同强连通分量中编号最小点 
            vis[v]=0;
        } while (v!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    memset(pre,INF,sizeof(pre));
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    if(block==1){
     cout <<"1"<< endl; 
     return 0; 
    }

    for(int i=1;i<=n;i++){
        for(int j=head[i];j!=-1;j=edge[j].next){
            int u=color[i];
            int v=color[edge[j].v];//判断u和v是不是在同一个强连通分量
            if(u!=v)in[v]++;//如果不是u指向v，v就记录入度 
        }
    }
    for(int i=1;i<=block;i++){//此处已经进行完压缩，压缩后还有block个点 
        if(!in[i]) //如果一个点没有入度 
        p.push_back(pre[i]);
    }
    sort(p.begin(),p.end());

    cout<<p.size()<<endl;
    for(int i=0;i<p.size();i++) cout<<p[i]<< " ";
    cout<<endl;
    return 0;
}