模拟赛题讲解[8]

来自 Roundgod 2022-07-27 noi.ac #2681

题目描述：

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

对于图中的每个顶点 $v$ ，你需要判断它属于以下哪种:

如果不存在从 $1$ 到 $v$ 的路径，输出 $0$ 。

如果存在恰好一条从 $1$ 到 $v$ 的路径，输出 $1$ 。

如果存在多于一条且有限的从 $1$ 到 $v$ 的路径，输出 $2$ 。

如果存在无限条从 $1$ 到 $v$ 的路径，输出 $3$ 。

输入格式：

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

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

题目保证图中不包含任何重边和自环。

输出格式：

在一行中输出 $n$ 个在 $\{0,1,2,3\}$ 中的数字，第 $i$ 个表示顶点 $i$ 属于的种类。

输入1：

输出1：

3 3 3

输入2：

5 0

输出2：

1 0 0 0 0

输入3：

输出3：

1 1 2 1

数据范围：

对于 $50\%$ 的数据，$1\leq n\leq 10^5,~1\leq m\leq 5\times 10^5$ ，并且保证图中不存在环。

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

题解：

注意是路径，不是简单路径！

不难想到，先强连通分量缩点一下

如果存在一条 $1$ 到 $v$ 的路径包含了一个强连通分量大小超过 $1$ 的结点

那么他们的路径就有无数条

其他么简单 $\text{topo}$ 一下就好了，或者 $\text{bfs}$ 估计也是可以的

~~然后q779又写挂了23333~~

时间复杂度 $O(n+m)$

代码：

#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
#define N (int)(1e5+15)
bool vis[N];
vector<int> g1[N],g2[N],vec[N];
int n,m,idx,scnt,in[N],inc[N];
int sz[N],f[N],ok[N],scc[N],dfn[N];
void addEdge(int u,int v)
{
    g1[u].push_back(v);
    g2[v].push_back(u);
}
void dfs1(int u)
{
    vis[u]=1;
    for(int v : g1[u])
        if(!vis[v]) dfs1(v);
    dfn[++idx]=u;
}
void dfs2(int u,int id)
{
    scc[u]=id; ++sz[id];
    for(int v : g2[u])
        if(!scc[v]) dfs2(v,id);
}
void kosaraju()
{
    for(int i=1; i<=n; i++)
        if(!vis[i]) dfs1(i);
    for(int i=n; i>=1; i--)
        if(!scc[dfn[i]])
        {
            ++scnt;
            dfs2(dfn[i],scnt);
        }
}
void topo()
{
    queue<int> q; ok[scc[1]]=1; f[scc[1]]=1;
    for(int i=1; i<=scnt; i++)
        if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        if(ok[u]&&sz[u]>1) inc[u]=1;
        for(int v : vec[u])
        {
            ok[v]|=ok[u]; inc[v]|=inc[u];
            f[v]=min(2ll,f[u]+f[v]);
            if(!(--in[v])) q.push(v);
        }
    }
    for(int i=1,u; i<=n; i++)
    {
        u=scc[i];
        if(!ok[u]) cout << "0";
        else if(inc[u]) cout << "3";
        else cout << f[u];
        cout << " \n"[i==n];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        addEdge(u,v);
    }
    kosaraju();
    for(int i=1; i<=n; i++)
        for(int j : g1[i])
        {
            int u=scc[i],v=scc[j];
            if(u!=v) vec[u].push_back(v),++in[v];
        }
    topo();
    return 0;
}