fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. public class Node
  6. {
  7. 	public int id;
  8.     public Node next;
  9.     public int indegree = 0;
  10.     public bool visited = false;
  11. }
  12. public class Test
  13. {
  14. 	public static void Main()
  15. 	{
  16.  
  17. 		// read number of nodes of the graph
  18. 		int n = Convert.ToInt32(Console.ReadLine());
  19.  
  20. 		Node []nodes = new Node[n];
  21.  
  22. 		// initiate nodes
  23. 		for (int i=0;i<n;i++)
  24. 			nodes[i]=new Node{id = i};
  25.  
  26. 		// reading input and initializing indegrees
  27. 		for (int i=0;i<n;i++)
  28. 		{
  29. 			// Each vertex has outgoing edge, so always there is a "next" neighbour
  30. 			var next = Convert.ToInt32(Console.ReadLine());
  31.  
  32. 			nodes[i].next = nodes[next];	
  33. 			nodes[next].indegree++;
  34. 		}
  35.  
  36. 		// Removing vertices of indegree zero recursively.
  37. 		// The code runs in O(n), in fact, it visits each edge only once, so it 
  38. 		// is O(|E|), but as every vertex has out degree one, |E|=O(|V|).
  39. 		for (int i=0;i<n;i++)
  40. 		{
  41. 				var current = nodes[i];
  42.  
  43. 				while (current != null && current.indegree == 0)
  44. 				{
  45. 					current.next.indegree--;
  46. 					var tmp = current.next;
  47. 					nodes[current.id] = null;
  48. 					current = tmp;
  49. 				}
  50. 		}
  51.  
  52. 		// Find All Cycles and Write Them in Console
  53. 		var cycles = new List<List<int>>();
  54. 		var count = 0;
  55. 		for (int i=0;i<n;i++)
  56. 		{
  57. 			if (nodes[i]!=null&& !nodes[i].visited)
  58. 			{
  59. 				cycles.Add(new List<int>());
  60. 				var current = nodes[i];
  61.  
  62. 				while (!current.visited)
  63. 				{
  64. 					cycles[count].Add(current.id);
  65. 					nodes[current.id].visited = true;
  66. 					current = current.next;
  67. 				}
  68. 				count++;
  69. 			}
  70. 		}
  71.  
  72. 		// Print cycles and find largest cycle and its length
  73. 		if (cycles.Count > 0)
  74. 		{
  75. 			Console.WriteLine("All cycles:");
  76. 			for (int i=0;i<cycles.Count;i++)
  77. 				Console.WriteLine(String.Join(", ", cycles[i]));
  78.  
  79. 			int maxLength = cycles.Max(x=>x.Count);
  80. 			Console.WriteLine("Maximum cycle length is: " + maxLength);
  81.  
  82. 			 Console.WriteLine("Largest cycle is: " +
  83. 			 					String.Join(", ",cycles.FirstOrDefault( x=>x.Count==maxLength)));
  84. 		}
  85. 		else
  86. 			Console.WriteLine("There is no cycle in the graph");
  87. 	}
  88. }
Success #stdin #stdout 0.01s 29800KB
comments (?)
stdin
copy 
28
1
2
3
4
5
4
4
6
7
8
4
10
11
12
5
14
15
16
21
25
22
25
19
20
18
27
19
22
stdout
copy 
All cycles:
4, 5
19, 25, 27, 22
Maximum cycle length is: 4
Largest cycle is: 19, 25, 27, 22
https://ideone.com/boY5U2
language:
C# (gmcs 5.20.1)
created:
8 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!