PAT1122 Hamiltonian Cycle (25 分) 欧拉回路、图论

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<vector<int>>v;
int n,m;;
bool hamCycle(vector<int>a){
    vector<bool>visit(n+1,false);
    if(a.size()!=n+1||a[0]!=a[a.size()-1])return false;
    visit[a[0]]=true;
    for(int i=1;i<a.size();i++){
        if((visit[a[i]]==true&&i!=a.size()-1)||v[a[i-1]][a[i]]!=1)  //该点（非路径最后一点）没被访问过，并且前后两点存在路径
            return false;
        else visit[a[i]]==true;
    }
    return true;
}
int main() {
    int a,b;
    cin>>n>>m;        //n个顶点，m条边
    v.resize(n+1,vector<int>(n+1,0));
    for(int i=0;i<m;i++){
        cin>>a>>b;
        v[a][b]=v[b][a]=1;
    }
    int k,num;
    cin>>k;
    for(int i=0;i<k;i++){
        cin>>num;
        vector<int>path;
        for(int j=0;j<num;j++){
            cin>>a;
            path.push_back(a);
        }
        printf("%sn",hamCycle(path)?"YES":"NO");
    }
    system("pause");
    return 0;
}

最后

以上就是任性早晨为你收集整理的PAT1122 Hamiltonian Cycle (25 分) 欧拉回路、图论的全部内容，希望文章能够帮你解决PAT1122 Hamiltonian Cycle (25 分) 欧拉回路、图论所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。