CareerCup

I think we can create a linked list from directory elements and do the check for "loop in linked list"

I have a bit confusion in the question, how can C be the child of both A and B, and if the argument is that B can again have folders of same name, the how will we come to know about cycle.
so considering C the child of A only ( and not B ) I have the following solution.
We can create an array of size 130 ( we could have done it in size 52 but this will be simple to understand )
in every statement:
array[firstRightElement], array[2ndRightElement], array[nextRightElement]=LeftElement;

so for above example:
array[B],array[C], array[a]=A;
similarly array[C],[D],[b],[c] will be B;
array[A] & [d] will be D

now the array will look something like this {D,A,A,B.... }
start from left most index and for every value try tracing its path..like starting from first, A whose parent is D, look for array[D] parent B, look for array[B] parent A so index=traced value.

You can do a DFS, and when you find a back-edge, you have a cycle in the graph.

Treat this as a graph and try to do a topological ordering of the nodes... If the order isn't found it has a cycle.

#include <iostream>
#include <stack>
#include <hash_set>

#define N 26

struct node
{
	int adjVex;
	node* next;
}adj[N];

int inDegree[N];
std::hash_set<int> map;

void init()
{
	memset(inDegree, 0, sizeof(inDegree));
	for(int i = 0; i < N; i++)
	{
		adj[i].adjVex = i;
		adj[i].next = NULL;
	}
};

void create(int u, int v)
{
	if(map.find(u) == map.end())
		map.insert(u);
	if(map.find(v) == map.end())
		map.insert(v);

	node* n = new node();
	n->adjVex = v;
	n->next = adj[u].next;
	adj[u].next = n;
	inDegree[v]++;
};

void printAdjList()
{
	std::cout << "Adj list:\n";
	for(int i = 0; i < N; i++)
	{
		char curElem = adj[i].adjVex + 'A';
		node* n = adj[i].next;

		bool printBreak = false;
		if(n)
		{
			printBreak = true;
			std::cout << curElem << " ";
		}

		while(n)
		{
			char cur = n->adjVex + 'A';
			std::cout << cur << " ";
			n = n->next;
		}
		if(printBreak)
			std::cout << "\n";
	}
};

bool topo()
{
	std::stack<int> st;
	//int cnt = 0;
	for(int i = 0; i < N; i++)
	{
		if(inDegree[i] == 0 && map.find(i) != map.end())
			st.push(i);
	}

	int top;
	std::cout << "Topo result:\n";
	while(!st.empty())
	{
		top = st.top();
		st.pop();
		char cur = top + 'A';
		std::cout << cur << " ";
		//cnt++;
		
		node* n = adj[top].next;
		while(n)
		{
			int k = n->adjVex;
			inDegree[k]--;
			if(inDegree[k] == 0)
				st.push(k);
			n = n->next;
		}
	}
	std::cout << "\n";

	for(int i = 0; i < N; i++)
	{
		if(inDegree[i] != 0)
			return false;
	}

	return true;
};

int main()
{
	int total;
	std::cout << "Put the total of the pairs: ";
	std::cin >> total;

	init();
	char u, v;
	std::cout << "-u- -v-\n";
	while(total--)
	{
		std::cin >> u >> v;
		create(u - 'A', v - 'A');
	}

	printAdjList();

	int canTopo = topo();

	if(!canTopo)
		std::cout << "This graph could not be topoed!\n"; 

	return 0;

}

use hash maps or floydd's cycle finding aldo
first one is much better