fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. using namespace std;
  5. bool found=false;
  6. void dfs(map<int,map<int,int> >& Map,map<int,int>& Map2,int i,int parent,vector<int> path)
  7. {
  8. 	if(found == true)
  9. 	{
  10. 		return;
  11. 	}
  12.  
  13. 	if(Map2.count(i) >0)
  14. 	{
  15. 		if(path.size() > 2)
  16. 		{
  17. 			found=true;
  18. 			vector<int> V;
  19. 			int count1=1;
  20. 			V.push_back(i+1);
  21. 			for(int j=path.size()-1;j>=0;j--)
  22. 			{
  23. 				V.push_back(path[j]+1);
  24. 				count1++;
  25. 				if(path[j] == i)
  26. 				{
  27. 					break;
  28. 				}
  29. 			}
  30.  
  31. 			cout<<count1<<endl;;
  32. 			for(int i=0;i<V.size();i++)
  33. 			{
  34. 				cout<<V[i]<<" ";
  35. 			}
  36. 			cout<<endl;
  37. 		}
  38. 		return;
  39. 	}
  40. 	Map2[i]=1;
  41. 	path.push_back(i);
  42. 	for(auto it=Map[i].begin();it!=Map[i].end();it++)
  43. 	{
  44. 		if(it->first == parent)
  45. 		{
  46. 			continue;
  47. 		}
  48. 		else
  49. 		{
  50. 			dfs(Map,Map2,it->first,i,path);
  51. 		}
  52.  
  53. 	}
  54. 	path.pop_back();
  55.  
  56. }
  57.  
  58.  
  59. int main() {
  60.  
  61. 	int n,m;
  62. 	cin>>n>>m;
  63.  
  64. 	map<int,map<int,int> > Map;
  65. 	for(int i=0;i<m;i++)
  66. 	{
  67. 		int a,b;
  68. 		cin>>a>>b;
  69. 		Map[a-1][b-1]=1;
  70. 		Map[b-1][a-1]=1;
  71. 	}
  72.  
  73. 	map<int,int> Map2;
  74. 	found=false;
  75. 	for(int i=0;i<n;i++)
  76. 	{
  77. 		if(Map2.count(i) <= 0)
  78. 		{
  79. 			vector<int> path;
  80. 			dfs(Map,Map2,i,-1,path);
  81. 		}
  82. 	}
  83.  
  84. 	if(found == false)
  85. 	{
  86. 		cout<<"IMPOSSIBLE"<<endl;
  87. 	}
  88.  
  89.  
  90. 	return 0;
  91. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5 6
1 3
1 2
5 3
1 5
2 4
4 5
stdout
copy 
5
1 5 4 2 1
https://ideone.com/Hy17BU
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!