题目链接
#include<stdio.h> #include<stdlib.h> #include<string.h> int mp[110][110]; bool vis[110]; int n, m; void DFS(int s) { for(int i=0;i<n;i++) { if(mp[s][i]&&vis[i]==0) { vis[i]=1; printf(" %d",i); DFS(i); } } } int main() { int t, u, v; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(mp,0,sizeof(mp)); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); mp[u][v]=mp[v][u]=1; } printf("0"); memset(vis,0,sizeof(vis)); vis[0]=1; DFS(0); printf("\n"); } return 0; }
优化：
#include <iostream> #include <algorithm> #include <string> #include <stack> #include <queue> using namespace std; const int maxn = 101; int mp[maxn][maxn]; bool vis[maxn+maxn]; int n, m; queue <int> que; void init() { while(!que.empty()) { que.pop(); } for(int i=0; i<maxn; ++i) for(int j=0; j<maxn; ++j) mp[i][j] = 0; for(int i=0;i<2*maxn;++i) vis[i] = false; } void dfs(int s) { for(int i=0;i<n;++i) if(mp[s][i]&&!vis[i]) { vis[i] = true; que.push(i); dfs(i); } } void print_que() { while(que.size() > 1) { cout<<que.front()<<" "; que.pop(); } cout<<que.front()<<endl; } int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { cin>>n>>m; init(); for(int i=0;i<m;++i) { int a, b; cin>>a>>b; mp[a][b]=mp[b][a]=1; } vis[0]=true; que.push(0); dfs(0); print_que(); } return 0; }c++栈实现：
#include <iostream> #include <algorithm> #include <string> #include <stack> using namespace std; const int maxn = 101; int mp[maxn][maxn]; bool vis[maxn+maxn]; int n, m; stack <int> stk; void init() { while(!stk.empty()) stk.pop(); for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) mp[i][j] = 0; for(int i=0;i<n;++i) vis[i] = false; } void dfs_stack(int x) { int node; int count = 1; cout<<x; vis[x] = true; node = x; stk.push(x); ///开始的节点入栈 while(count < n) ///still has node not visited { int j; /// 所有被访问的节点依次入栈，只有node当找不到下一个相连的节点时，才使用出栈节点 for(j=0; j<n; j++) { if(mp[node][j] && !vis[j]) { vis[j] = true; cout<<" "<<j; count++; stk.push(j); //push node j break; } } if(j == n) ///与node相连的节点都已经被访问过，所以需要从stack里取出node的上一个节点，再看该节点是否有相连的节点未被访问 { stk.pop(); node = stk.top(); } else ///找到与node相连并且未被访问的节点， node = j; } cout<<endl; } int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { cin>>n>>m; init(); for(int i=0;i<m;++i) { int a, b; cin>>a>>b; mp[a][b]=mp[b][a]=1; } dfs_stack(0); } return 0; }
