526互联

7999: 路径图 并查集

发布时间 2023-08-10 20:47:14作者: CRt0729

描述

 

给定一个n个顶点(1~n编号)，m条边的简单无向图，判断是否是一个路径图。

路径图要求：必须存在一个顶点序列v1, v2, ..., vn，它是1~n的一个排列，且对于任何1<=i<=n-1，vi和vi+1之间有边相连，而对于任何1<=i, j<=n(其中|i-j|>=2)，vi和vj之间没有边相连。

 

输入

 

第一行为两个正整数n和m(2<=n<=2*105, 0<=m<=2*105)。

接下来有m行，每行两个整数u和v（1<= u, v<= n），表示u和v之间有一条边。

 

输出

 

如果图是“路径图”输出Yes，否则输出No

 

路径图：可以理解为m条边刚好构成了一颗树，n个点之间连接了n-1条边，有回路不行，且每个点都要有边相连

通过并查集如果find(x)==find(y)那么就是有回路，通过并查集后的f[i]==i来统计父节点的个数，如果大于1那么也不行

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int f[N];
int find(int x)
{
    if(f[x]!=x)f[x] = find(f[x]);
    return f[x];
}
void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    f[fy] = fx;
}
int main()
{
    int n,m,flag = 1;
    cin >> n >> m;
    for(int i=1;i<=n;i++)f[i] = i;
    for(int i=1;i<=m;i++)
    {
        int x,y; scanf("%d %d",&x,&y);
        if(find(x)!=find(y))merge(x,y);
        else flag = 0;
    }
    int sum = 0;
    for(int i=1;i<=n;i++)
        if(f[i]==i)sum++;
    if(sum>1 || !flag)cout << "No";
    else cout << "Yes";
    return 0;
}