题目传送门

大致题意:

给定一张有向图,求能被所有其他点到达的点的个数。不保证图连通。

$1\leq n \leq 10^4,1\leq m\leq 5*10^4$


Solution

暴力显然不可取。

image.png

发现样例是个这样的图,最终答案是只有3一个点。

进而联想到,如果图中存在一个,当然里面的点可以互相到达,并且可以到达环上每个点可以到达的点。

或者说,我们可以把这个环抽象成一个点,这个环所连出的边就是其中包含的点连出的边。所连向的也是原本连向的点所在的环。

把所有环都缩点之后,发现就是一个有向无环图。

若存在能被所有点都到达的点,那么它所在的环一定没有向外连边。否则连出去之后不可能再回来(无环)。

(以下在图中讨论的“点”,实际是原图中的“环”)

在这张DAG(有向无环图)上看,还能注意到它一定是唯一一个这样的点(不向外连边,即出度为0)。

所以答案仅可能出现在缩点之后,有且仅有一个出度为零的点,并且数值为这个环包含的点的个数。

所以具体实现即用强连通分量缩点,缩点之后统计出度,如果有且仅有一个出度为0的点,那么答案就是这个点的$size$。

至于强连通分量缩点,可以阅读我这篇博文:

code:

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
const int M=200010;
int head[M],to[M],nxt[M],cnt;
void add(int u,int v)
{
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
int dfn[N],low[N],idx;
int in[N]; 
int stk[N],scnt,top;
int num[N],sz[N];
void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    in[u]=1,stk[++top]=u;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);low[u]=min(low[u],low[v]);
        }
        else if(in[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        scnt++;
        int k;
        do
        {
            k=stk[top--];
            num[k]=scnt;
            in[k]=0;
            sz[scnt]++;
        }
        while(k!=u);
    }
}
int out[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;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);
    for(int u=1;u<=n;u++)
    {
        for(int i=head[u];i;i=nxt[i])
        {
            int v=to[i];
            int x=num[u],y=num[v];
            if(x!=y)out[x]++;
        }
    }
    int id=-1;
    for(int i=1;i<=scnt;i++)
        if(!out[i])
            if(id==-1)id=i;
            else id=-2;
    printf("%d\n",id>0?sz[id]:0);
    return 0;
}
最后修改:2020 年 08 月 20 日 10 : 46 PM