diff options
Diffstat (limited to '03-algorithms_on_graphs/01-decomposition')
10 files changed, 104 insertions, 0 deletions
diff --git a/03-algorithms_on_graphs/01-decomposition/00_decomposition_problems.pdf b/03-algorithms_on_graphs/01-decomposition/00_decomposition_problems.pdf Binary files differnew file mode 100644 index 0000000..fb304b4 --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/00_decomposition_problems.pdf diff --git a/03-algorithms_on_graphs/01-decomposition/01-reachability/reachability.cpp b/03-algorithms_on_graphs/01-decomposition/01-reachability/reachability.cpp new file mode 100644 index 0000000..cb2e76f --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/01-reachability/reachability.cpp @@ -0,0 +1,26 @@ +#include <iostream> +#include <vector> + +using std::vector; +using std::pair; + + +int reach(vector<vector<int> > &adj, int x, int y) { + //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); + adj[y - 1].push_back(x - 1); + } + int x, y; + std::cin >> x >> y; + std::cout << reach(adj, x - 1, y - 1); +} diff --git a/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/01 b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/01 new file mode 100644 index 0000000..d7bb894 --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/01 @@ -0,0 +1,6 @@ +4 4 +1 2 +3 2 +4 3 +1 4 +1 4 diff --git a/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/01.a b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/01.a new file mode 100644 index 0000000..d00491f --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/01.a @@ -0,0 +1 @@ +1 diff --git a/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/02 b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/02 new file mode 100644 index 0000000..e27d40b --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/02 @@ -0,0 +1,4 @@ +4 2 +1 2 +3 2 +1 4 diff --git a/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/02.a b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/02.a new file mode 100644 index 0000000..573541a --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/01-reachability/tests/02.a @@ -0,0 +1 @@ +0 diff --git a/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp b/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp new file mode 100644 index 0000000..8e6b531 --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/02-connected_components/connected_components.cpp @@ -0,0 +1,24 @@ +#include <iostream> +#include <vector> + +using std::vector; +using std::pair; + +int number_of_components(vector<vector<int> > &adj) { + int res = 0; + //write your code here + return res; +} + +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); + adj[y - 1].push_back(x - 1); + } + std::cout << number_of_components(adj); +} diff --git a/03-algorithms_on_graphs/01-decomposition/02-connected_components/tests/01 b/03-algorithms_on_graphs/01-decomposition/02-connected_components/tests/01 new file mode 100644 index 0000000..174151f --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/02-connected_components/tests/01 @@ -0,0 +1,3 @@ +4 2 +1 2 +3 2 diff --git a/03-algorithms_on_graphs/01-decomposition/02-connected_components/tests/01.a b/03-algorithms_on_graphs/01-decomposition/02-connected_components/tests/01.a new file mode 100644 index 0000000..0cfbf08 --- /dev/null +++ b/03-algorithms_on_graphs/01-decomposition/02-connected_components/tests/01.a @@ -0,0 +1 @@ +2 diff --git a/03-algorithms_on_graphs/01-decomposition/check b/03-algorithms_on_graphs/01-decomposition/check new file mode 100755 index 0000000..b73ff99 --- /dev/null +++ b/03-algorithms_on_graphs/01-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 + |