KETYES - Editorial

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah

DIFFICULTY:

SIMPLE

PREREQUISITES:

Graph Theory, Graph Traversal

PROBLEM:

Given a tree and a node, find the distance from the root to the node.

QUICK EXPLANATION:

Traverse the tree using BFS or DFS and store the distance of each node from the root in a linked list, till the required node is found.

EXPLANATION:

You need to find the distance of the given node from the root node (root node which is always 0). For that you have to start traversing the tree from the root node. For traversing the tree you can either use BFS or DFS (read more here). Every time a new node, lets say A, is found from another node, lets call it B, you add 1 to the distance of B from root and call it the distance of A from root. You store that distance in a linked list. When you find the required node you break from the loop, and print the required distance.

Following is the code with explanation in comments

		Stack<int>st=new Stack<int>();//declare a stack
		List<int>done=new List<int>();//declare a linked list to store already visited nodes
		List<int>dist=new List<int>();//declare another linked list to store distance of current node from popped node
		st.Push(0);//pushing root node, the source node
		done.Add(0);//adding root node to linked list, cause its visited
		dist.Add(0);//adding distance of root node from root node
		while(st.Count>0)//till all nodes are visited this will run
		{
			int now=st.Pop();//popping current node
			int curdist=dist[done.IndexOf(now)];//extracting distance of current node from root node
			for(int i=0;i<n;i++)//iterating through all nodes
			{
			
				if(arr[now,i]==1)//if its neighbour of popped node then this will be true
				{
					if(!done.Contains(i))//if its not visited already
					{
						done.Add(i);//add node to linked list
						dist.Add(curdist+1);//add extracted distance+1 to distance linked list
						st.Push(i);//push the node to the stack
					}
				}
			}
		}
		Console.WriteLine(dist[done.IndexOf(find)]);//print the required distance

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found above.
Tester’s solution can be found above.