看的别的大佬的,,自己还不是很理解。
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<math.h>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;int n,m;
vector <int> g[25];
int vis[1<<22];
int shoot[1<<22];
int pre[1<<22];int bfs(int st){queue<int>q;vis[st]=1;q.push(st);while (!q.empty()){int tmp=q.front();q.pop();if (!tmp)return true;for (int i=0;i<n;i++){
//枚举射击的点,射击的点也有可能是当前猴子不再的点,所以得遍历所有的点 int nst=0;//用来保存射击后的猴可能跑到那个状态 for (int j=0;j<n;j++){
//枚举猴子可能在的点(即状态为1) if (j!=i&&(tmp&(1<<j))){ //判断tmp第j位是不是1for (int k=0;k<g[j].size();k++){//判断当前状态中猴子是否可能在j这个点 //如果在的话,下一枪可能跑到其邻接点 int v=g[j][k];//直接或就行 nst|=(1<<v); //把第v+1位改成1}}}if (vis[nst])continue;//如果当前状态已经有了,就跳过 vis[nst]=1;//标记这个状态已经有了 pre[nst]=tmp;//保存当前这个状态的父节点为tmp shoot[nst]=i;//保存这个状态是打的第i个点 q.push(nst);}} return 0;
}int main ()
{while(scanf ("%d%d",&n,&m)){if (n==0&&m==0) break;for (int i=0;i<=n;i++){g[i].clear();}int u,v;for (int i=0;i<m;i++){scanf ("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}int st=(1<<n)-1;for (int i=0;i<=st;i++){vis[i]=0;}if (bfs(st)){vector<int>ans;int now=0;while (1){if (now==st)break;//到达初始状态则停止 ans.push_back(shoot[now]);//将每个状态打的点放进向量 now=pre[now];}printf ("%d:",ans.size());for (int i=ans.size()-1;i>=0;i--){printf (" %d",ans[i]);}printf ("\n");}else {//cout<<"";printf ("Impossible\n");}} return 0;
}