PAT甲级1126 Eulerian Path：[C++题解] 欧拉路径、并查集，测试点4有问题请进来

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PAT甲级1126 Eulerian Path：[C++题解] 欧拉路径、并查集，测试点4有问题请进来，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2003字，纯文字阅读大概需要3分钟。

内容图文

文章目录

• • 题目分析
  • 题目链接

题目分析

来源：acwing

分析：
欧拉图： 1）连通 2）度都为偶数
半欧拉图：欧拉路径：2）连通2） 度为奇数的结点有两个，其他度都是偶数
非欧拉图：不是欧拉图和半欧拉图。
判连通使用并查集。

ac代码（并查集）

#include<bits/stdc++.h>
using namespace std;
const int N  =510;
int cnt[N];//每个点的度数
int n ,m;
bool g[N][N];//有边

int p[N];

//找根
int find(int x){
    if(p[x] != x) p[x] =find(p[x]);
    return p[x];
}


int main(){
    
    cin >> n>> m;
    for(int i = 1; i<=n; i++) p[i] =i;
    
    while(m--){
        int a, b;
        cin >> a  >> b;
        cnt[a]++,cnt[b]++;
         p[find(a)] = find(b); //合并集合，如果已经是同一个集合会自动忽略
    }
    //统计度
    int one =0;  //统计度为奇数的结点个数
    for(int i = 1 ;i <=n; i++){
        if( cnt[i] &1 ) one ++;
    }
    //判连通性
    //用set保存根结点个数
    set<int> root;
    for(int i=1; i<=n; i++)
        root.insert(find(i));
    int num =root.size();

    
    cout<<cnt[1];
    for(int i =2; i<= n; i++) cout<<" "<<cnt[i];
    cout<<endl;
    if(num==1 &&one == 0) cout<<"Eulerian"<<endl;
    else if(num ==1&& one == 2) cout<<"Semi-Eulerian"<<endl;
    else cout<<"Non-Eulerian"<<endl;
}

wa1个点的代码（同样使用并查集）
下面的代码测试点4有问题
错误原因：统计错了度为偶数的结点个数，统计度为奇数的就没有问题了。也就是最后if、else有问题

#include<bits/stdc++.h>
using namespace std;
const int N  =510;
int cnt[N];//每个点的度数
int n ,m;
bool g[N][N];//有边

int p[N];

int find(int x){
    if(p[x] != x) p[x] =find(p[x]);
    return p[x];
}


int main(){
    
    cin >> n>> m;
    for(int i = 1; i<=n; i++) p[i] =i;
    
    while(m--){
        int a, b;
        cin >> a  >> b;
        cnt[a]++,cnt[b]++;
        if(find(a)!=find(b))  p[find(a)] = find(b);
    }
    //统计度
    int one = 0 ,two =0;
    for(int i = 1 ;i <=n; i++){
        if(cnt[i]&1) one++;
        if(cnt[i] && cnt[i] % 2 ==0) two ++;
    }
    //判连通性
    //用set保存根结点个数
    set<int> root;
    for(int i=1; i<=n; i++)
        root.insert(find(i));
    int num =root.size();

    
    cout<<cnt[1];
    for(int i =2; i<= n; i++) cout<<" "<<cnt[i];
    cout<<endl;
    if(num==1 &&two == n) cout<<"Eulerian"<<endl;
    else if(num ==1&& two == n -2) cout<<"Semi-Eulerian"<<endl; //这里错了，不能保证one有2个，因为n可能是奇数
    else cout<<"Non-Eulerian"<<endl;
}

题目链接

PAT甲级1126 Eulerian Path

内容总结

以上是互联网集市为您收集整理的PAT甲级1126 Eulerian Path：[C++题解] 欧拉路径、并查集，测试点4有问题请进来全部内容，希望文章能够帮你解决PAT甲级1126 Eulerian Path：[C++题解] 欧拉路径、并查集，测试点4有问题请进来所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端