Scribd
Upload
4 views3 pages

Strongly Connected Components in Graphs

The document contains a C++ implementation for finding strongly connected components in a directed graph using depth-first search (DFS). It defines functions to perform DFS, identify components, and construct a condensed adjacency list. The main function reads input for the number of vertices and edges, builds the adjacency list, and outputs the strongly connected components.

Uploaded by

naveenthumati095
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views3 pages

Strongly Connected Components in Graphs

The document contains a C++ implementation for finding strongly connected components in a directed graph using depth-first search (DFS). It defines functions to perform DFS, identify components, and construct a condensed adjacency list. The main function reads input for the number of vertices and edges, builds the adjacency list, and outputs the strongly connected components.

Uploaded by

naveenthumati095
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

SCC

vector<bool> vis;

void dfs(ll v,vector<vector<ll>> &adj,vector<ll> &output)


{
vis[v]=true;
for(auto u:adj[v])
{
if(vis[u]) continue;
dfs(u,adj,output);
}
[Link](v);
}

void strongly_connected_components(vector<vector<ll>> &adj


,vector<vector<ll>> &components,vector<vector<ll>> &adj_cond)
{
ll n=[Link]();
vector<ll> order;
[Link](n,false);
for(ll i=0;i<n;i++)
{
if(!vis[i])
{
dfs(i,adj,order);
}
}
reverse(all(order));
vector<vector<ll>> adj_t(n);
for(ll u=0;u<n;u++)
{
for(auto v:adj[u])
{
adj_t[v].pb(u);
}
}
[Link](n,false);
vector<ll> roots(n,0);
for(auto v:order)
{
if(!vis[v])
{
vector<ll> component;
dfs(v,adj_t,component);
[Link](component);
ll root=*min_element(all(component));
for(auto u:component)
{
roots[u]=root;
}
}
}
adj_cond.assign(n,{});
for(ll v=0;v<n;v++)
{
for(auto u:adj[v])
{
if(roots[u]!=roots[v])
{
adj_cond[roots[v]].pb(roots[u]);
}
}
}
}

void solve()
{
ll n,m;
cin>>n>>m;
vector<vector<ll>> adj(n);
for(ll i=0;i<m;i++)
{
ll u,v;
cin>>u>>v;
adj[u].pb(v);
}
vector<vector<ll>> components;
vector<vector<ll>> adj_cond;
strongly_connected_components(adj,components,adj_cond);
for(auto &v:components)
{
for(auto el:v)
{
cout<<el<<" ";
}
cout<<endl;
}
}

You might also like