What’s wrong in my implementation of strongly connected components. I am getting the wrong answer on the test case
input :
9 10
0 1
1 2
2 3
3 0
2 4
4 5
5 6
6 4
7 6
7 8
ouput :
1:7->/
2:8->/
3:0->3->2->1->/
4:4->6->5->/
// Kosaraju's algorithm to find strongly connected components in C++
#include <iostream>
#include <vector>
#include <stack>
#define ll long long
using namespace std;
ll n,m,u,v,cnt=0;
vector<ll>adj1[1000];
vector<ll>adj2[1000];
bool vis1[1000],vis2[1000];
stack<ll>s;
void dfs1(ll node)
{
vis1[node]=1;
for(ll neighbour:adj1[node])
{
if(!vis1[neighbour])
{
dfs1(neighbour);
}
}
s.push(node);
}
void dfs2(ll node)
{
vis2[node]=1;
cout<<node<<"->";
for(ll neighbour:adj2[node])
{
if(!vis2[neighbour])
{
dfs2(neighbour);
}
}
}
int main()
{
cin>>n>>m;
while(m--)
{
cin>>u>>v;
adj1[u].push_back(v);
adj2[v].push_back(u);
}
dfs1(1);
while(!s.empty())
{
ll cur=s.top();
s.pop();
if(!vis2[cur])
{
cnt++;
cout<<cnt<<":";
dfs2(cur);
cout<<"/"<<endl;
}
}
return 0;
}