fork download 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public class Node
  6. {
  7. 	public bool UsedOnce;
  8.     public int Id;
  9.     public bool Visited;
  10.     public Node[] Children;
  11.  
  12.     public Node(int id, Node[] children)
  13.     {
  14.     	UsedOnce = false;
  15.     	Visited = false;
  16.     	Id = id;
  17.     	Children = children;
  18.     }
  19.  
  20.     public Node(int id)
  21.     {
  22.     	UsedOnce = false;
  23.     	Visited = false;
  24.     	Id = id;
  25.     	Children = new Node[0];
  26.     }
  27. }
  28.  
  29. public class Test
  30. {
  31. 	public static void DFS(Node node)
  32. 	{
  33. 	    if (node.Children.Length == 0) // if it is a leaf (no children) - output
  34. 	    {
  35. 	    	OutputAndMarkAsUsed();
  36. 	    	return;
  37. 	    }
  38.  
  39. 	    foreach (var child in node.Children)
  40. 	    {
  41. 	        if (!child.Visited) // for every not visited children call DFS
  42. 	        {
  43. 	            child.Visited = true;
  44. 	            currentPath.Add(child);
  45. 	            DFS(child); 
  46. 	            currentPath.Remove(child);
  47. 	            child.Visited = false;
  48. 	        }
  49. 	    }
  50. 	}
  51.  
  52. 	private static void OutputAndMarkAsUsed()
  53. 	{
  54. 		int startId = 0;
  55.     	for (int i = 0; i < currentPath.Count - 1; i++)
  56.     		if (currentPath[i + 1].UsedOnce == false) 
  57.     		{
  58.     			startId = i;
  59.     			break;
  60.     		}
  61.  
  62.     	for (int i = startId; i < currentPath.Count; i++)
  63.     	{
  64.     		Console.Write("{0} ", currentPath[i].Id);
  65.     		currentPath[i].UsedOnce = true;
  66.     	}
  67.  
  68.         Console.WriteLine();
  69.  
  70.         return;
  71. 	}
  72.  
  73. 	private static List<Node> currentPath = new List<Node>();
  74.  
  75. 	public static void Main()
  76. 	{
  77. 		var root = new Node(1, new [] {
  78. 			new Node(2, new [] {
  79. 				new Node(5),
  80. 				new Node(6)
  81. 			}),
  82. 			new Node(3, new [] {
  83. 				new Node(7)
  84. 			}),
  85. 			new Node(4, new [] {
  86. 				new Node(8),
  87. 				new Node(9)
  88. 			})
  89. 		});
  90.  
  91. 		root.Visited = true;
  92.         currentPath.Add(root);
  93.         DFS(root); 
  94. 	}
  95. }
Success #stdin #stdout 0.06s 24048KB
comments (?)
stdin 
Standard input is empty
stdout 
1 2 5 
2 6 
1 3 7 
1 4 8 
4 9
https://ideone.com/JbCNNp
language:
C# (gmcs 5.20.1)
created:
8 years ago
visibility:
secret

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!