fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Solution {
  6.     int n;
  7.     vector<vector<int>> adjList;
  8.     bool directed = true;
  9. public:
  10.          bool dfs(int v, 
  11.          vector<vector<int>>& adjList,
  12.          vector<bool>& discovered,
  13.          vector<bool>& processed,
  14.          vector<int>& parent)
  15. 		{     
  16. 		    bool ans = false;
  17. 		    discovered[v] = true;
  18.  
  19. 		    for(auto x : adjList[v])
  20. 		    {
  21. 		        if(!discovered[x])
  22. 		        {
  23. 		            parent[x] = v;  
  24. 		            ans |= dfs(x, adjList, discovered, processed, parent);
  25. 		        }
  26. 		        else if((!processed[x] && parent[v]!=x) || directed)
  27. 		        {
  28. 		            if(parent[x]!=v)
  29. 		            {
  30. 		                return true;
  31. 		            }
  32. 		        }
  33. 		    }
  34.  
  35. 		    processed[v] = true;
  36. 		    return ans;
  37. 		}
  38.  
  39.     bool validTree(int n, vector<vector<int>>& edges) {
  40.         this->n = n;
  41.         adjList.resize(n);
  42.         vector<bool> discovered(n, false);
  43.         vector<bool> processed(n, false);
  44.         vector<int> parent(n, -1);
  45.  
  46. 	    for(auto& x : edges)
  47.         {
  48.             adjList[x[0]].emplace_back(x[1]);
  49.         }
  50.  
  51. 		bool ans = false;
  52.         for(int i = 0; i < n; ++i)
  53.         {
  54.             if(!discovered[i])
  55.             {
  56.                 ans |= (dfs(i, adjList, discovered, processed, parent));
  57.             	if(ans)
  58.             		return ans;
  59.             }
  60.         }
  61.  
  62.         return ans;
  63.     }
  64.  
  65. };
  66.  
  67.  
  68. int main() {
  69. 	int n = 4;
  70. 	vector<vector<int>> edges(n);
  71. 	edges[0] = {0,2};
  72. 	edges[1] = {3,0};
  73. 	edges[2] = {3,1};
  74. 	edges[3] = {1,2};
  75. 	Solution s;
  76. 	cout<<s.validTree(n,edges)<<endl;
  77.  
  78. 	return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/9o0trZ
language:
C++ (gcc 8.3)
created:
2 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!