fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. #define max 110
  5. int adj[max][max];
  6. int status[max];
  7. int n,e;
  8. using namespace std;
  9. void reset_adj_stat()
  10. {
  11. 	for(int i=1;i<=n;i++)
  12. 	{
  13. 		status[i]=0;
  14. 		for(int j=1;j<=n;j++)
  15. 		{
  16. 			adj[i][j]=0;
  17. 		}
  18. 	}
  19. }
  20. void set(int s)
  21. {
  22. 	for(int i=1;i<=n;i++)
  23. 	{
  24. 		if((adj[s][i]==1)&&(status[i]==0))
  25. 		{
  26. 			status[i]=s;
  27. 		}
  28. 	}
  29. }
  30. void reset(int s)
  31. {
  32. 	for(int i=1;i<=n;i++)
  33. 	{
  34. 		if((adj[s][i]==1)&&(status[i]==s))
  35. 		{
  36. 			status[i]=0;
  37. 		}
  38. 	}
  39. }
  40. int check()
  41. {
  42. 	for(int i=1;i<=n;i++)
  43. 	{
  44. 		if(status[i]==0)
  45. 		{
  46. 			return 0;
  47. 		}
  48. 	}
  49. 	return 1;
  50. }
  51.  
  52. int get_optimal(int cnt,int &loc)
  53. {
  54. 	int m=0;
  55. 	int c=check();
  56. 	if(c)
  57. 	  return 0;
  58. 	for(int i=1;i<=n;i++)
  59. 	{
  60. 		if(status[i]==0)
  61. 		{
  62. 			status[i]=i;
  63. 			set(i);
  64. 			int k=1+get_optimal(cnt+1,loc);
  65. 			if(k>m)
  66. 			{
  67. 			  m=k;
  68. 			  if(cnt==0)
  69. 			  {
  70. 			    loc=i;
  71. 			  }	
  72. 			}
  73. 			status[i]=0;
  74. 			reset(i);
  75. 		}
  76. 	}
  77. 	return m;
  78. }
  79. void print_path(int &loc,int k)
  80. {
  81. 	for(int i=0;i<k;i++)
  82. 	{
  83. 		cout<<loc<<" ";
  84. 	    status[loc]=loc;
  85. 	    set(loc);
  86. 	    int cnt=0;loc=0;
  87. 	    int p=get_optimal(cnt,loc);
  88. 	}
  89. }		
  90. int main()
  91. { 
  92.    int t,v1,v2,cnt,loc,k;
  93.    cin>>t;
  94.    for(int i=0;i<t;i++)
  95.    {
  96.    	 cin>>n>>e;
  97.    	 reset_adj_stat();
  98.    	 cnt=0;
  99.    	 for(int j=1;j<=e;j++)
  100.    	 {
  101.    	 	cin>>v1>>v2;
  102.    	 	adj[v1][v2]=1;
  103.    	 	adj[v2][v1]=1;
  104.    	 }
  105.    	 int k=get_optimal(cnt,loc);
  106.    	 if(k!=0)
  107.    	 {
  108.    	 cout<<k<<" "<<"\n";
  109.    	 print_path(loc,k);
  110.    	 cout<<"\n";
  111.     }
  112.     else
  113.     {
  114.     	cout<<k<<" "<<"\n"<<"\n";
  115.     }
  116.    }
  117.     return 0;
  118. }
  119.  
  120.  
Success #stdin #stdout 0s 3396KB
comments (?)
stdin
copy 
2
0 0
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
stdout
copy 
0 

3 
1 4 5
https://ideone.com/Yf5DLo
language:
C++ (gcc 8.3)
created:
10 years 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!