蓝桥杯 ADV-319 VIP试题 哈密尔顿回路（试题解析）

试题 算法提高 哈密尔顿回路

提交此题   评测记录  

资源限制

时间限制：2.0s   内存限制：256.0MB

问题描述

　　给出一个有向图，输出这个图的一个哈密尔顿回路。

输入格式

　　输入的第一行包含两个整数n, m，分别表示图的点数和边数。

　　接下来m行，每行包含两个整数，表示一条边的起点和终点。

输出格式

　　输出一行，包含一个n个整数，表示一条哈密尔顿回路。如果没有回路，输出“No Answer””。

样例输入

3 3

1 2

2 3

3 1

样例输出

1 2 3

数据规模和约定

　　1<=n<=20，图中没有重边。

解题思路：从每个顶点开始BFS遍历，若所有节点都被访问过，则跳出循环，输出路径。然而，BFS访问的节点次序具有不确定性，只跑了42分。算法还不够精确。。。未完待续。。。

代码如下：

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

vector<vector<int> >    G(22);
int n,m;
int vis[22];
int pred[22];

void Read(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int s,e;
        cin>>s>>e;
        G[s].push_back(e);
    }
    
}

void init(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        pred[i]=i;
    }
}

int BFS(int S){
    queue<int>    Q;
    vis[S]=1;
    Q.push(S);
    int last=0;
    while(!Q.empty()){
        int V=Q.front();
        Q.pop();
        last=V;
        
        
        for(int i=0;i<G[V].size();i++){
            int to=G[V][i];
            if(vis[to]==0){
                pred[to]=V;
                vis[to]=1;
                Q.push(to);
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(vis[i]==0)
            return -1;
    }
    return last;
}

void Opt(){
    //尝试从每个顶点出发, 
    int flag=-1;
    for(int i=1;i<=n;i++){
        init();
        flag=BFS(i);
        if(flag>0){
            break;
        }        
    }
    if(flag>0){
        int pos=flag;
        vector<int>    res;
        res.push_back(pos);
        while(1){
            pos=pred[pos];
            res.push_back(pos);
            if(pred[pos]==pos){
                break;
            }
        } 
        
        for(int i=res.size()-1;i>=0;i--){
            cout<<res[i]<<" ";
        }
    }
    else{
        cout<<"No Answer"<<endl;
    }
    
    
}

int main(int argc, char** argv) {
    Read();
    Opt();

    return 0;
}