fork download
copy 
  1. // Wyszukiwanie cykli i ścieżek Hamiltona
  2. // Data: 10.02.2014
  3. // (C)2014 mgr Jerzy Wałaszek
  4. //---------------------------------------
  5.  
  6. #include <iostream>
  7. #include <iomanip>
  8.  
  9. using namespace std;
  10.  
  11. // Typy danych
  12.  
  13. struct SLel
  14. {
  15.   SLel * next;
  16.   int v;
  17. };
  18.  
  19. // Zmienne globalne
  20.  
  21. int m, n;                       // Liczba krawędzi i wierzchołków
  22. SLel **graf;                 // Tablica list sąsiedztwa
  23. int *S;                         // Tablica-stos
  24. int sptr;                       // Wskaźnik stosu
  25. bool *visited;                  // Tablica odwiedzin
  26.  
  27. // Rekurencyjna procedura wyznaczająca ścieżki i cykle Hamiltona
  28. // v-wierzchołek bieżący
  29. //--------------------------------------------------------------
  30. void DFSHamilton (int v)
  31. {
  32.   int i;
  33.   bool test;
  34.   SLel *p;
  35.  
  36.   S [sptr++] = v;             // Wierzchołek v na stos
  37.   if(sptr < n)                // Jest ścieżka Hamiltona?
  38.   {
  39.     visited [v] = true;       // Nie ma, odwiedzamy v
  40.     for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów v
  41.       if(!visited [p->v]) DFSHamilton (p->v); // Wywołanie rekurencyjne
  42.     visited [v] = false;      // Wycofujemy się z v
  43.   }
  44.   else                          // Jest ścieżka Hamiltona
  45.   {
  46.     test = false;               // Zakładamy brak cyklu
  47.     for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów
  48.       if(! (p->v))          // Jeśli sąsiadem jest wierzchołek 0, 
  49.       {
  50.         test = true;            // to mamy cykl
  51.         break;
  52.       }
  53.  
  54.     if(test) cout << "Hamiltonian Cycle :";
  55.     else     cout << "Hamiltonian Path  :";
  56.  
  57.     for(i = 0; i < sptr; i++) // Wypisujemy ścieżkę Hamiltona
  58.       cout << setw (3) << S [i];
  59.     if(test) cout << setw (3) << 0; // Dla cyklu dopisujemy wierzchołek startowy
  60.     cout << endl;
  61.   }
  62.   sptr--;                       // Wierzchołek v usuwamy ze stosu
  63. }
  64.  
  65. // **********************
  66. // *** PROGRAM GŁÓWNY ***
  67. // **********************
  68.  
  69. int main()
  70. {
  71.   int i, v1, v2;
  72.   SLel *p, *r;
  73.  
  74.   cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi
  75.  
  76.   // Tworzymy tablice dynamiczne
  77.  
  78.   graf    = new SLel * [n];
  79.   visited = new bool [n];
  80.   for(i = 0; i < n; i++)
  81.   {
  82.     graf [i]    = NULL;
  83.     visited [i] = false;
  84.   }
  85.   S = new int [n];
  86.   sptr = 0;
  87.  
  88.   // Odczytujemy definicje krawędzi grafu
  89.  
  90.   for(i = 0; i < m; i++)
  91.   {
  92.     cin >> v1 >> v2;
  93.     p = new SLel;
  94.     p->v = v2;
  95.     p->next = graf [v1];
  96.     graf [v1] = p;
  97.   }
  98.  
  99.   cout << endl;
  100.  
  101.   // Wyświetlamy ścieżki i cykle Hamiltona
  102.  
  103.   DFSHamilton (0);
  104.  
  105.   // Usuwamy zmienne dynamiczne
  106.  
  107.   delete [] visited;
  108.   delete [] S;
  109.  
  110.   for(i = 0; i < n; i++)
  111.   {
  112.     p = graf [i];
  113.     while(p)
  114.     {
  115.       r = p;
  116.       p = p->next;
  117.       delete r;
  118.     }
  119.   }
  120.  
  121.   delete [] graf;
  122.  
  123.   return 0;}
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5 14
0 2
1 0
1 2
1 3
2 0
2 1
3 0
3 1
3 2
4 0
4 1
4 2
4 3
4 4
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/KA6LAX
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
7 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!