1341：【例题】一笔画问题
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。
【输入】
第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。
【输出】
欧拉路或欧拉回路,输出一条路径即可。
【输入样例】
5 5
1 2
2 3
3 4
4 5
5 1
【输出样例】
1 5 4 3 2 1
【提示】
【数据范围】
对于100%的数据：1 < n < 100,1 < m < 2000。
1. #include <bits/stdc++.h> 2. using namespace std; 3. int mp[1005][1005]; 4. int du[1005]; 5. int path[1005],k; 6. int n,m,a,b; 7. void dfs(int x){//搜索路径 8. for(int i=1;i<=n;i++) 9. if(mp[x][i]==1){ 10. mp[x][i]=mp[i][x]=0; 11. dfs(i); 12. } 13. path[k++]=x; 14. } 15. int main() { 16. cin>>n>>m; 17. for(int i=1;i<=m;i++){ 18. cin>>a>>b; 19. mp[a][b]=mp[b][a]=1; 20. du[a]++; 21. du[b]++; 22. } 23. int start=1; 24. for(int i=1;i<=n;i++)//寻找奇点 25. if(du[i]%2!=0) {start=i;break;} 26. dfs(start); 27. for(int i=0;i<k;i++) cout<<path[i]<<" "; 28. return 0; 29. }
