題意:圖中有N個點,每個點至少和其他(N+1)/2個點連接,問能否找到一個有N個點的環(即不存在重復的點,N個點都在內)。
分析:數據量小,直接暴力深搜,起點直接設為點1(一定能找到環 或者 環本身不存在)。
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一類的 #define MAX 200 #define INF 0x7FFFFFFF # define eps 1e-5 //#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛 using namespace std; int map[MAX][MAX]; int path[MAX]; int vis[MAX]; int n,m,ok; void init() { memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); } void dfs(int u0,int v,int cur) { path[cur] = v; if(cur == n && map[u0][v]) { ok = 1; return ; } for(int i=1; i<=n; i++) { if(vis[i] == 0 && map[v][i]) { vis[i] = 1; dfs(u0,i,cur+1); vis[i] = 0 ; } if(ok == 1) return ; } } int main() { while(cin >> n >> m) { int a,b; memset(map,0,sizeof(map)); for(int i=0; i<m; i++) { scanf("%d%d",&a,&b); map[a][b] = 1; map[b][a] = 1; } ok = 0; init(); vis[1] = 1; dfs(1,1,1); if(ok == 1) { for(int i=1; i<n; i++) { cout << path[i]<< ' '; } cout << path[n] << endl; } else cout << "no solution" << endl; } return 0; } #include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一類的 #define MAX 200 #define INF 0x7FFFFFFF # define eps 1e-5 //#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛 using namespace std; int map[MAX][MAX]; int path[MAX]; int vis[MAX]; int n,m,ok; void init() { memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); } void dfs(int u0,int v,int cur) { path[cur] = v; if(cur == n && map[u0][v]) { ok = 1; return ; } for(int i=1; i<=n; i++) { if(vis[i] == 0 && map[v][i]) { vis[i] = 1; dfs(u0,i,cur+1); vis[i] = 0 ; } if(ok == 1) return ; } } int main() { while(cin >> n >> m) { int a,b; memset(map,0,sizeof(map)); for(int i=0; i<m; i++) { scanf("%d%d",&a,&b); map[a][b] = 1; map[b][a] = 1; } ok = 0; init(); vis[1] = 1; dfs(1,1,1); if(ok == 1) { for(int i=1; i<n; i++) { cout << path[i]<< ' '; } cout << path[n] << endl; } else cout << "no solution" << endl; } return 0; }