Raj's Blog


Main Page


Strongly Connected Components




                    
        int sz = 200005;
        vector<VII> adj(sz),rev(sz);
        vector<bool> vis(sz,false);
        vector<VII> SCC(sz);
        int comp = 0;
        VII topo;
        void dfs_forward(int u)
        {
            for(auto it:adj[u])
            {
                if(!vis[it])
                {
                    vis[it] = true;
                    dfs_forward(it);
                }
            }
            topo.pb(u);
        }

        void dfs_backward(int u)
        {
            SCC[comp].pb(u);
            for(auto it:rev[u])
            {
                if(!vis[it])
                {
                    vis[it] = true;
                    dfs_backward(it);
                }
            }
        }
        main()
        {
        int n,m;
            cin >> n>>m;
            for (int i = 1; i <= m; ++i)
            {
                int x, y;
                cin >> x >> y;
                adj[x].pb(y);
                rev[y].pb(x);
            }
            for (int i = 1; i <= n;++i)
            {
                if(!vis[i])
                {
                    vis[i] = 1;
                    dfs_forward(i);
                }
            }
            reverse(all(topo));
            vis.assign(sz, false);

            for(auto x:topo)
            {
                if(!vis[x])
                {
                    vis[x] = true;
                    comp++;
                    dfs_backward(x);
                }
            }

            for (int i = 1; i <= comp;++i)
            {
                for(auto sc:SCC[i])
                    cout << sc << ' ';

                cout << '\n';
            }
        }