From a8a76010ed04bc931a09121847a93c3ca468e41a Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jul 2017 12:28:21 +0200 Subject: Update articulationPoints.cpp fixed articulation points for disconnected graphs and automaticly set isArt for roots --- graph/articulationPoints.cpp | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) (limited to 'graph/articulationPoints.cpp') diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index aa73486..460919d 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -1,13 +1,13 @@ // Laufzeit: O(|V|+|E|) -vector< vector > adjlist; +vector> adjlist; vector isArt; vector d, low; -int counter, root; // root >= 2 <=> Wurzel Artikulationspunkt +int counter, root, rootCount; // root >= 2 <=> Wurzel Artikulationspunkt vector bridges; // Nur fuer Brücken. -void dfs(int v, int parent) { // Mit parent=-1 aufrufen. - d[v] = low[v] = counter++; - if (parent == 0) root++; +void dfs(int v, int parent = -1) { + d[v] = low[v] = ++counter; + if (parent == root) ++rootCount; for (auto w : adjlist[v]) { if (!d[w]) { @@ -20,10 +20,14 @@ void dfs(int v, int parent) { // Mit parent=-1 aufrufen. }}} void findArticulationPoints() { - counter = 1; // Nicht auf 0 setzen! + counter = 0; low.resize(adjlist.size()); d.assign(adjlist.size(), 0); isArtPoint.assign(adjlist.size(), false); bridges.clear(); //nur fuer Bruecken - for (int v = 0; v < (int)adjlist.size(); v++) if (!d[v]) dfs(v, -1); -} + for (int v = 0; v < (int)adjlist.size(); v++) { + if (!d[v]) { + root = v; rootCount = 0; + dfs(v); + if (rootCount > 1) isArt[v] = true; +}}} -- cgit v1.2.3 From ea229a62473986aa76edf9b890c7c3592ef27b46 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jul 2017 12:30:58 +0200 Subject: Update articulationPoints.cpp updated coments --- graph/articulationPoints.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'graph/articulationPoints.cpp') diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index 460919d..7b81c91 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -2,7 +2,7 @@ vector> adjlist; vector isArt; vector d, low; -int counter, root, rootCount; // root >= 2 <=> Wurzel Artikulationspunkt +int counter, root, rootCount; // rootCount >= 2 <=> root Artikulationspunkt vector bridges; // Nur fuer Brücken. void dfs(int v, int parent = -1) { -- cgit v1.2.3 From 4576d70b03ebb89d7747541bafa1e9018a39699b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jul 2017 14:09:47 +0200 Subject: Update articulationPoints.cpp root has an other calculation for isArt --- graph/articulationPoints.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'graph/articulationPoints.cpp') diff --git a/graph/articulationPoints.cpp b/graph/articulationPoints.cpp index 7b81c91..e7139d0 100644 --- a/graph/articulationPoints.cpp +++ b/graph/articulationPoints.cpp @@ -12,7 +12,7 @@ void dfs(int v, int parent = -1) { for (auto w : adjlist[v]) { if (!d[w]) { dfs(w, v); - if (low[w] >= d[v]) isArt[v] = true; + if (low[w] >= d[v] && v != root) isArt[v] = true; if (low[w] > d[v]) bridges.push_back(ii(v, w)); low[v] = min(low[v], low[w]); } else if (w != parent) { -- cgit v1.2.3