Написал небольшую программу для поиска шарниров, вот теперь возник вопрос как можно распараллелить этот алгоритм?.
Почитал о поиске в глубину, пишут что алгоритм плохо поддается распараллеливанию, но плохо не значит что не поддается
[syntax lang="cpp"]
//#include "stdafx.h"
#include <iostream>
#include<vector>
#include<fstream>
#include <algorithm>
using namespace std;
const int MAXN = 20001;
vector<int> g[MAXN], g1[MAXN];
bool used[MAXN],is_added[MAXN];
int timer, tin[MAXN], fup[MAXN], points[MAXN];
int results[MAXN];
int k = 0;
void null(bool mas[MAXN]){
for (int i = 0; i<MAXN; i++)
mas[i] = false;
}
void null(int m[MAXN]){
for (int i = 0; i<MAXN; i++)
m[i] = -1;
}
void init(int m[MAXN], int n){
for (int i = 0; i<n; i++)
m[i] = -1;
}
void dfs(int v, int p = -1) { //поиск шарниров
used[v] = true;
tin[v] = fup[v] = timer++;
int children = 0;
for (size_t i = 0; i<g[v].size(); ++i) {
int to = g[v][i];
if (to == p) continue;
if (used[to])
fup[v] = min(fup[v], tin[to]);
else {
dfs(to, v);
fup[v] = min(fup[v], fup[to]);
if (fup[to] >= tin[v] && p != -1){
if (!is_added[v]) {
points[k] = v;
is_added[v] = true;
k++;
}
}
++children;
}
}
if (p == -1 && children > 1){
if (!is_added[v]) {
points[k] = v;
is_added[v] = true;
k++;
}
}
}
void read(int& n){
ifstream in("input.txt");
int m, a, b;
in >> n >> m;
for (int i = 0; i<m; i++){
in >> a >> b;
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}
}
void bubble_sort(int *data, int size) {
int i, j;
for (i = 0; i < size; ++i) {
for (j = size - 1; j > i; --j) {
if (data[j] > data[j - 1]) {
int t = data[j - 1];
data[j - 1] = data[j];
data[j] = t;
}
}
}
}
int main() {
int n; int i; vector<int> g1[MAXN];
ofstream out("output.txt");
null(points);
read(n);
// init(results, n);
timer = 0;
for (i = 0; i < n; i++){
used[i] = false;
is_added[i] = false;
}
dfs(0);
i = 0;
bubble_sort(points, MAXN);
while ((i<MAXN) && (points[i] != -1)){
i++;
}
out << i << endl;
i = MAXN-1;
while ((i >= 0)){
if (points[i] != -1)
out << points[i] + 1 << endl;
i--;
}
return 0;
}
[/syntax]
искал в разных книгах и в гугле как такие узлы называются, не мог найти