Algorithms : add 03-algorithms_on_graphs 02-decomposition

17 files changed, 160 insertions, 0 deletions

diff --git a/03-algorithms_on_graphs/02-decomposition/00_decomposition_problems.pdf b/03-algorithms_on_graphs/02-decomposition/00_decomposition_problems.pdf
new file mode 100644
index 0000000..3e02c61
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/00_decomposition_problems.pdf
diff --git a/03-algorithms_on_graphs/02-decomposition/01-acyclicity/acyclicity.cpp b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/acyclicity.cpp
new file mode 100644
index 0000000..9cd27e6
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/acyclicity.cpp
@@ -0,0 +1,22 @@
+#include <iostream>
+#include <vector>
+
+using std::vector;
+using std::pair;
+
+int acyclic(vector<vector<int> > &adj) {
+  //write your code here
+  return 0;
+}
+
+int main() {
+  size_t n, m;
+  std::cin >> n >> m;
+  vector<vector<int> > adj(n, vector<int>());
+  for (size_t i = 0; i < m; i++) {
+    int x, y;
+    std::cin >> x >> y;
+    adj[x - 1].push_back(y - 1);
+  }
+  std::cout << acyclic(adj);
+}
diff --git a/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/01 b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/01
new file mode 100644
index 0000000..010643f
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/01
@@ -0,0 +1,5 @@
+4 4
+1 2
+4 1
+2 3
+3 1
diff --git a/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/01.a b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/01.a
new file mode 100644
index 0000000..d00491f
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/01.a
@@ -0,0 +1 @@
+1
diff --git a/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/02 b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/02
new file mode 100644
index 0000000..a65b977
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/02
@@ -0,0 +1,8 @@
+5 7
+1 2
+2 3
+1 3
+3 4
+1 4
+2 5
+3 5
diff --git a/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/02.a b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/02.a
new file mode 100644
index 0000000..573541a
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/01-acyclicity/tests/02.a
@@ -0,0 +1 @@
+0
diff --git a/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/01 b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/01
new file mode 100644
index 0000000..c4a403a
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/01
@@ -0,0 +1,4 @@
+4 3
+1 2
+4 1
+3 1
diff --git a/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/01.a b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/01.a
new file mode 100644
index 0000000..58167da
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/01.a
@@ -0,0 +1 @@
+4 3 1 2 
diff --git a/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/02 b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/02
new file mode 100644
index 0000000..e1e8f05
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/02
@@ -0,0 +1,8 @@
+5 7
+2 1
+3 2
+3 1
+4 3
+4 1
+5 2
+5 3
diff --git a/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/02.a b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/02.a
new file mode 100644
index 0000000..e40f56d
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/02-toposort/tests/02.a
@@ -0,0 +1 @@
+5 4 3 2 1 
diff --git a/03-algorithms_on_graphs/02-decomposition/02-toposort/toposort.cpp b/03-algorithms_on_graphs/02-decomposition/02-toposort/toposort.cpp
new file mode 100644
index 0000000..bc37a24
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/02-toposort/toposort.cpp
@@ -0,0 +1,32 @@
+#include <iostream>
+#include <algorithm>
+#include <vector>
+
+using std::vector;
+using std::pair;
+
+void dfs(vector<vector<int> > &adj, vector<int> &used, vector<int> &order, int x) {
+  //write your code here
+}     
+
+vector<int> toposort(vector<vector<int> > adj) {
+  vector<int> used(adj.size(), 0);
+  vector<int> order;
+  //write your code here
+  return order;
+}
+
+int main() {
+  size_t n, m;
+  std::cin >> n >> m;
+  vector<vector<int> > adj(n, vector<int>());
+  for (size_t i = 0; i < m; i++) {
+    int x, y;
+    std::cin >> x >> y;
+    adj[x - 1].push_back(y - 1);
+  }
+  vector<int> order = toposort(adj);
+  for (size_t i = 0; i < order.size(); i++) {
+    std::cout << order[i] + 1 << " ";
+  }
+}
diff --git a/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp
new file mode 100644
index 0000000..0ad7b62
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp
@@ -0,0 +1,24 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+using std::vector;
+using std::pair;
+
+int number_of_strongly_connected_components(vector<vector<int> > adj) {
+  int result = 0;
+  //write your code here
+  return result;
+}
+
+int main() {
+  size_t n, m;
+  std::cin >> n >> m;
+  vector<vector<int> > adj(n, vector<int>());
+  for (size_t i = 0; i < m; i++) {
+    int x, y;
+    std::cin >> x >> y;
+    adj[x - 1].push_back(y - 1);
+  }
+  std::cout << number_of_strongly_connected_components(adj);
+}
diff --git a/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01 b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01
new file mode 100644
index 0000000..010643f
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01
@@ -0,0 +1,5 @@
+4 4
+1 2
+4 1
+2 3
+3 1
diff --git a/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01.a b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01.a
new file mode 100644
index 0000000..0cfbf08
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01.a
@@ -0,0 +1 @@
+2
diff --git a/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02 b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02
new file mode 100644
index 0000000..e1e8f05
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02
@@ -0,0 +1,8 @@
+5 7
+2 1
+3 2
+3 1
+4 3
+4 1
+5 2
+5 3
diff --git a/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02.a b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02.a
new file mode 100644
index 0000000..7ed6ff8
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02.a
@@ -0,0 +1 @@
+5
diff --git a/03-algorithms_on_graphs/02-decomposition/check b/03-algorithms_on_graphs/02-decomposition/check
new file mode 100755
index 0000000..b73ff99
--- /dev/null
+++ b/03-algorithms_on_graphs/02-decomposition/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+RED="\033[0;31m"
+GREEN="\033[0;32m"
+BROWN="\033[0;33m"
+
+BIN=/tmp/bin
+OUTA=/tmp/_outa
+OUTB=/tmp/_outb
+GPP_OPTS="-std=c++11 -O2"
+
+for path in $(find -name \*.cpp | sort); do
+    src=${path##*/}
+    dir=${path%/*}
+    echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET"
+    pushd $dir >/dev/null || exit 1
+    echo -e "   ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1
+    if [ -d tests ]; then
+        echo -e "   ${RED}check $GREEN$src$RESET"
+        for t in $(find ./tests -name "*[^a~]"|sort); do
+            if [ -f $t -a -f "$t.a" ]; then
+                cat $t | $BIN > $OUTA
+                cat $t.a > $OUTB
+                cmp $OUTA $OUTB >/dev/null
+                if [ $? -ne 0 ]; then
+                    echo -e "     $BROWN$t$RESET is ${RED}KO$RESET"
+                else
+                    echo -e "     $BROWN$t$RESET is ${GREEN}ok$RESET"
+                fi
+            fi
+        done
+    else
+        echo -e "   ${RED}no tests$RESET"
+    fi
+    popd > /dev/null
+done
+