using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace IsATree { public class CheckTree { static void addAdj(int index , string source, List > adj, List> edges) { foreach(KeyValuePair edge in edges) { if (source == edge.Key ) { adj[index].Add(edge.Value); } } } static int Vertices_count; static List> adj; //adj = new List>(Vertices_count); static void SetStatic(string[] vert , int vertCount ,List> adj ) { Vertices_count = vert.Count(); //List> adj; adj = new List>(Vertices_count); } public static bool IsTree(string[] vertices, List> edges) { int counter = vertices.Count(); adj = new List>(counter); SetStatic( vertices , counter , adj ); bool [] IsChecked = new bool [vertices.Count()]; bool [] InStack = new bool[vertices.Count()]; for (int j = 0; j < vertices.Count(); j++) { adj.Add(new List()); //addAdj(j ,vertices[j].ToString() , adj , edges); } for (int j = 0; j < vertices.Count(); j++) { //adj.Add(new List()); addAdj(j, vertices[j].ToString(), adj, edges); } for (int i = 0; i < vertices.Count(); i++) { if (checkCycle(i, IsChecked, InStack ,vertices , edges)) return true; } return false; } static bool checkCycle(int i , bool [] IsChecked , bool [] InStack ,string[] vertices, List> edges) { // adj = new List>(); if (i == InStack.Count()) return false; if (InStack[i] == true) return true; if (IsChecked[i] == true) return false; InStack[i] = true; IsChecked[i] = true; List leaves = adj[i] ; // List leaves = (from kvp in edges select kvp.Key).ToList(); foreach (string leaf in leaves) { if (checkCycle(Int32.Parse(leaf) , IsChecked , InStack , vertices,edges)) return true; } InStack[i] =false; return false; } //=============================================================================== //=============================================================================== } }

Graph Has Cycles or not