#include <bits/stdc++.h>
using namespace std;
multiset<unsigned long long> connectedComp;
unsigned long long int counter = 0;
unsigned long long int numComponents = 0;
class Graph{
public:
unsigned long long int size;
list<unsigned long long> *adjList;
bool *visited;
stack<unsigned long long int> s;
Graph(unsigned long long int);
void addEdge(unsigned long long int,unsigned long long int);
void reverse();
void DFS1(unsigned long long int);
unsigned long long int DFS2(unsigned long long int);
void Kosaraju(void);
void initialize(void);
};
Graph::Graph(unsigned long long int s){
size = s;
adjList = new list<unsigned long long>[size];
visited = new bool[size];
}
void Graph::addEdge(unsigned long long int src,unsigned long long int dest){
adjList[src].push_back(dest);
}
void Graph::DFS1(unsigned long long int src) {
initialize();
stack<int> stack;
stack.push(src);
stack.push(src);
while(!stack.empty()){
src = stack.top();
stack.pop();
if(!visited[src]){
visited[src] = true;
}
else if(visited[src]) s.push(src);
for(auto it = adjList[src].begin();it!= adjList[src].end();it++){
if(!visited[*it]){ stack.push(*it); stack.push(*it);}
}
}
}
void Graph::initialize(void){
for(unsigned long long int i = 0;i<size;i++) visited[i] = false;
}
unsigned long long int Graph::DFS2(unsigned long long int src){
counter = 0;
stack<int> stack;
stack.push(src);
while (!stack.empty()) {
counter++;
src = stack.top();
stack.pop();
if (!visited[src])
visited[src] = true;
for (auto i = adjList[src].begin(); i != adjList[src].end(); ++i)
if (!visited[*i])
stack.push(*i);
}
return counter;
}
void Graph::reverse(){
list<unsigned long long> *tempAdj = new list<unsigned long long>[size];
list<unsigned long long>::iterator it;
for(unsigned long long int i = 0;i<size;i++){
it = adjList[i].begin();
for(it;it!= adjList[i].end();it++){
tempAdj[*it].push_back(i);
}
}
adjList = tempAdj;
}
void Graph::Kosaraju(void){
for(unsigned long long int i = 0;i<size;i++){
if(!visited[i]) DFS1(i);
}
reverse();
initialize();
while (!s.empty()){
unsigned long long int v = s.top(); s.pop();
if (!visited[v])
{
connectedComp.insert(DFS2(v));
visited[v] = true;
numComponents++;
}
}
}
int main(void){
Graph g(11);
g.addEdge(0,2);
g.addEdge(1,0);
g.addEdge(2,1);
g.addEdge(2,3);
g.addEdge(3,4);
g.addEdge(4,5);
g.addEdge(5,3);
g.addEdge(6,5);
g.addEdge(6,7);
g.addEdge(7,8);
g.addEdge(8,9);
g.addEdge(9,6);
g.addEdge(9,10);
g.Kosaraju();
for(auto it = connectedComp.rbegin();it != connectedComp.rend();it++){
cout<<*it<<endl;
}
}
Я сделал реализацию алгоритма Косараю для сильно связанных компонентов, однако моя реализация вычисляет неверное число связанных компонентов, один из которых находится в данном коде. Интересно, что не так с точки зрения логики c. Например, мой код работает с таким порядком узлов: Graph g (5); g.addEdge (1, 0); g.addEdge (0, 2); g.addEdge (2, 1); g.addEdge (0, 3); g.addEdge (3, 4);