DAG graph check done. Not too bad after Java version.

1 files changed, 31 insertions, 15 deletions

diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp
index a950767..3fdd795 100644
--- a/Sources/GraphAlgo.cpp
+++ b/Sources/GraphAlgo.cpp
@@ -5,34 +5,51 @@
 #include <algorithm>
 
 using std::vector;
-using std::pair;
+//using std::pair;
 
-void explore(vector<vector<int>> &adj, vector<int> &visited, int v) {
+void explore(vector<vector<int>> &adj, int v, vector<int> &visited, vector<int> &prev,
+		vector<int> &postv, vector<int> &clock) {
 	visited.push_back(v);
+	prev[v] = clock[0];
+	clock[0] = clock[0] + 1;
 
 	for (size_t i = 0; i < adj[v].size(); i++) {
 		if (std::find(visited.begin(), visited.end(), adj[v][i])
 				== visited.end())
-			explore(adj, visited, adj[v][i]);
+			explore(adj, adj[v][i], visited, prev, postv, clock);
 	}
+	postv[v] = clock[0];
+	clock[0] = clock[0] + 1;
+
 }
 
-int number_of_components(vector<vector<int> > &adj) {
+void dfs(vector<vector<int>> &adj, vector<int> &visited, vector<int> &prev,
+		vector<int> &postv, vector<int> &clock) {
+	for (size_t v = 0; v < adj.size(); v++) {
+		if (std::find(visited.begin(), visited.end(), v) == visited.end())
+			explore(adj, v, visited, prev, postv, clock);
+	}
+}
 
+int acyclic(vector<vector<int> > &adj) {
 	vector<int> visited;
-	int cc = 0;
-	for (size_t v = 0; v < adj.size(); v++) {
-		if (std::find(visited.begin(), visited.end(), v) == visited.end()) {
-			explore(adj, visited, v);
-			cc++;
+	vector<int> prev(adj.size(), 0);
+	vector<int> postv(adj.size(), 0);
+	vector<int> clock(1, 0);
+	dfs(adj, visited, prev, postv, clock);
+
+	for (size_t u = 0; u < adj.size(); u++) {
+		for (size_t i = 0; i < adj[u].size(); i++) {
+			if (postv[u] <= postv[adj[u][i]])
+				return 1;
 		}
 	}
-	return cc;
+	return 0;
 }
 
-//TEST(ConnectedComponents, cc1) {
-//	vector<vector<int>> adj = { { 1 }, {0, 2 }, { 1 }, { } };
-//	ASSERT_EQ(number_of_components(adj), 2);
+//TEST(Acyclicity, ac1) {
+//	vector<vector<int>> adj = { { 1 }, { 2 }, { 0 }, { 0 } };
+//	ASSERT_EQ(acyclic(adj), 1);
 //}
 
 int main() {
@@ -43,7 +60,6 @@ int main() {
     int x, y;
     std::cin >> x >> y;
     adj[x - 1].push_back(y - 1);
-    adj[y - 1].push_back(x - 1);
   }
-  std::cout << number_of_components(adj);
+  std::cout << acyclic(adj);
 }