fork download
copy 
  1. /*
  2. Input: {'a','p'}, {'d','p'}, {'h','a'}, {'h', 'd'} 
  3. Output - [p, a, d, h] 
  4.  
  5. p->a
  6.  
  7. */
  8.  
  9. #include <iostream>
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13.  
  14.  
  15. vector<char>  bfs (vector<vector<char>> & list)
  16. {
  17. 	vector<char> res;
  18. 	vector<char> empty;
  19. 	unordered_map<char,vector<char>> adj;
  20. 	unordered_set<char> distChars;
  21. 	unordered_map <char,int> indegree;
  22. 	for(int i=0;i<list.size();i++)
  23. 	{
  24. 		int x = list[i][0];
  25. 		int y = list[i][1];
  26. 		// y->x
  27. 		indegree[x]++;
  28. 		adj[y].push_back(x);
  29. 		distChars.insert(x);
  30. 		distChars.insert(y);
  31. 	}
  32. 	queue<char> q;
  33. 	for(auto z :distChars  )
  34. 	{
  35. 		if(indegree[z]==0)
  36. 		{
  37. 			q.push(z);
  38. 		}
  39. 	}
  40. 	//cout<<"qsize"<<q.size();
  41. 	while(q.size()>0)
  42. 	{
  43. 		char z = q.front();
  44. 		res.push_back(z);
  45. 		q.pop();
  46. 		for(auto adjChar : adj[z])
  47. 		{
  48. 			indegree[adjChar]--;
  49. 			if(indegree[adjChar]==0)
  50. 			{
  51. 				q.push(adjChar);
  52. 			}
  53. 		}
  54. 	}
  55. 	if(res.size() < distChars.size())
  56. 	{
  57. 		return empty;
  58. 	}
  59. 	return  res;
  60.  
  61. }
  62. int main() {
  63. 	// your code goes here
  64.  
  65. 	vector<vector<char>> list = {{'a','p'}, {'d','p'}, {'h','a'}, {'h', 'd'},{'a','h'}};
  66. 	vector<char> res;
  67. 	res = bfs (list);
  68. 	if(res.size()==0)
  69. 	{
  70. 		cout<<"Cycle is exisitng";
  71. 	}
  72. 	for(auto c : res)
  73. 	{
  74. 		cout<<c<<",";
  75. 	}
  76.  
  77. 	return 0;
  78. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Cycle is exisitng
https://ideone.com/8pqWvg
language:
C++ (gcc 8.3)
created:
8 hours 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!