模拟赛题讲解[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;
}