From ce845d792479e9c153274c2ad5a199a7f7c17a41 Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Sun, 13 Nov 2016 23:04:04 +0100 Subject: Algorithms : add 03-algorithms_on_graphs 02-decomposition --- .../03-strongly_connected/strongly_connected.cpp | 24 ++++++++++++++++++++++ .../03-strongly_connected/tests/01 | 5 +++++ .../03-strongly_connected/tests/01.a | 1 + .../03-strongly_connected/tests/02 | 8 ++++++++ .../03-strongly_connected/tests/02.a | 1 + 5 files changed, 39 insertions(+) create mode 100644 03-algorithms_on_graphs/02-decomposition/03-strongly_connected/strongly_connected.cpp create mode 100644 03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01 create mode 100644 03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/01.a create mode 100644 03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02 create mode 100644 03-algorithms_on_graphs/02-decomposition/03-strongly_connected/tests/02.a (limited to '03-algorithms_on_graphs/02-decomposition/03-strongly_connected') 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 +#include +#include + +using std::vector; +using std::pair; + +int number_of_strongly_connected_components(vector > adj) { + int result = 0; + //write your code here + return result; +} + +int main() { + size_t n, m; + std::cin >> n >> m; + vector > adj(n, vector()); + 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 -- cgit v1.2.3