题解 | #World Fragments I#

这场啥都不会，就会乱搞，嘤嘤嘤

写个E的题解吧。

首先，我们建一张图

然后，写一个dfs

最后，我们每次把边的顺序随机，跑几十次dfs

我们就得到了正确答案，好耶！

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

mt19937 rd(time(0));

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 ve(n+1,vector<int>());
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            ve[u].push_back(v);
        }
        auto get = [&](){
            vector<int> deep(n+1);
            deep[1] = 1;
            auto dfs = [&](auto dfs,int u)->void{
                for(auto &i : ve[u]){
                    if(deep[i]) continue;
                    deep[i] = deep[u] + 1;
                    dfs(dfs,i);
                }
            };
            dfs(dfs,1);
            return deep;
        };
        vector<int> ans;
        for(int i=1;i<=n;i++){
            sort(ve[i].begin(),ve[i].end());
        }
        ans=get();
        for(int i=1;i<=n;i++){
            reverse(ve[i].begin(),ve[i].end());
        }
        if(ans!=get()) goto no;
        for(int i=1;i<=50;i++){
            for(int i=1;i<=n;i++){
                shuffle(ve[i].begin(),ve[i].end(),rd);
            }
            if(ans!=get()) goto no;
        }
        cout<<"Yes"<<endl;
        if(0) no: cout<<"No"<<endl;
    }
}