2022 CCPC广州 C Customs Controls 2

Customs Controls 2

并查集 + 拓扑

看了题解之后补的，题解写挺好的

考虑到 \(1\) 距离相等的点进行并查集合并（指向同一个点的点，到 \(1\) 的距离相等），缩点后重新建边，判断是否有环，若有说明不成立

成立之后拓扑处理当前点的最大深度，这个深度就代表 \(1\) 到该点（缩点后的）的距离

接下来就好办了，有边 u -> v 的话，代表 \(val_v = dep_v - dep_u\)，枚举所有边算一下就行了

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<int>top;

int query(int x)
{
    return x == top[x] ? x : top[x] = query(top[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n, m;
        cin >> n >> m;
        vector<vector<int>>gra(n + 1), pre(n + 1), E(n + 1);
        top.resize(n + 1);
        for(int i=0; i<=n; i++) top[i] = i;
        for(int i=0; i<m; i++)
        {
            int a, b;
            cin >> a >> b;
            gra[a].push_back(b);
            pre[b].push_back(a);
        }
        for(int i=1; i<=n; i++)
        {
            if(pre[i].empty()) continue;
            int now = pre[i][0];
            for(int j=1; j<pre[i].size(); j++)
            {
                int a = query(now), b = query(pre[i][j]);
                if(a != b)
                    top[b] = top[a];
            }
        }
        vector<int>in(n + 1, 0), dep(n + 1, 1);
        for(int i=1; i<=n; i++)
        {
            for(int nex : gra[i])
            {
                E[query(i)].push_back(query(nex));
                in[query(nex)]++;
            }
        }
        queue<int>q;
        for(int i=1; i<=n; i++)
        {
            if(i != query(i)) in[i] = -1;
            else if(in[i] == 0) q.push(i);
        }
        while(q.size())
        {
            int now = q.front();
            q.pop();
            for(int nex : E[now])
            {
                if(--in[nex] == 0)
                {
                    q.push(nex);
                    dep[nex] = dep[now] + 1;
                }
            }
        }
        int f = 1;
        for(int i=1; i<=n; i++) if(in[i] > 0) f = 0;
        if(f == 0) {cout << "No\n"; continue;}
        cout << "Yes\n";
        vector<int>ans(n + 1, 1);
        for(int i=2; i<n; i++)
        {
            int nex = pre[i][0];
            ans[i] =  dep[query(i)] - dep[query(nex)];
        }
        for(int i=1; i<=n; i++)
        {
            if(i != 1) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }
    return 0;
}