官方题解

题目大意

判断是否存在一种将编号为 $1$ 到 $n$ 的 $n$ 个人的排列方式，使得以下 $m$ 个条件全部成立。

• 条件：第 $a_i$ 个人与第 $b_i$ 个人必须相邻。

解题思路

简单来说，题目就是要求我们构造一条链，满足所有点对相邻的条件。

如果要构成一条链，需要满足：

• 每个点的度最大为 $2$ 。
• 不存在环。

我们只需要判断以上两个条件是否都满足即可。对所有的点对关系建图，第一个条件直接记录每个点的度，判断是否存在点的度大于等于 $3$ 的；第二个条件用 $dfs$ 或并查集判断图中是否存在环即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

int n,m;
vector<int>v[N];
int in[N];
bool vis[N];
bool flag;

void dfs(int u,int fa){
    if(vis[u] || flag){
        flag=true;
        return;
    }
    vis[u]=true;
    
    for(auto x:v[u]){
        if(x==fa) continue;
        dfs(x,u);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
        in[a]++;
        in[b]++;
        if(in[a]>2 || in[b]>2) flag=true;
    }

    for(int i=1;i<=n;i++){
        if(vis[i]) continue;

        dfs(i,-1);
    }

    if(flag) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}