模拟赛题讲解[2]

来自 Roundgod 2022-07-25 noi.ac #2677

题目描述：

给定一个有向图 $G=(V,E)$ ，其中顶点个数 $|V|=n$ ，边数 $|E|=m$ 。顶点编号为 $1−N$ ，边的编号为 $1−M$ ，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$ 。

Makima会从图中的某个顶点出发并重复沿着某条有向边行走。你需要计算:存在多少个顶点 $v$ ，使得Makima可以从点 $v$ 出发无限地走下去?

输入格式：

输入第一行包含 $2$ 个整数 $n,m$ ，分别表示图的顶点数和图的边数。

接下来 $m$ 行，每行包含两个整数 $a_i,b_i(1\le a_i,b_i\le n,a_i\ne b_i)$ ，表示第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$ 。

输出格式：

在一行中输出一个整数，表示满足条件的顶点个数。

输入1：

输出1：

输入2：

3 2
1 2
2 1

输出2：

数据范围：

对于 $50\%$ 的数据，$1\le n\le 2000,~1\le m\le 10000$

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5,~1\le m\le 2\times 10^5$

题解：

这题还是比较简单的，赛时秒了

不难发现，如果一个结点出发可以走到一个环上

这个点、这个点到环的路径上的所有点以及所有能走到这个点的点都是满足要求的点

显然问题就变成了：找到哪些结点是死路（走不到环上）

考虑建反图然后跑 $\text{topo}$ 排序。

可以认为这个过程是，倒着思考，从死路出发，看看它能祸害多少结点

好像这个题可以用 $\text{Tarjan}$ ，不过我这个不太熟，等熟练了再说吧。

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(2e5+15)

int n,m,pos=1,head[N],in[N];
queue<int> q;
struct Edge{int u,v,next;} e[N];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n); read(m);
    for(int i=1,u,v; i<=m; i++)
    {
        read(u); read(v);
        addEdge(v,u); ++in[u];
    }
    int res=n;
    for(int i=1; i<=n; i++)
        if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        --res;
        for(int i=head[u]; i; i=e[i].next)
        {
            if(!(--in[e[i].v]))
                q.push(e[i].v);
        }
    }
    write(res);
    return 0;
}