Cod sursa(job #2972638)

Utilizator InsanekktVlad Matei Insanekkt Data 29 ianuarie 2023 21:33:47
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=100005;
int n, m, k;
vector <int> g[NMAX], revg[NMAX], comp[NMAX];
stack <int> st;
bool viz[NMAX];

void dfs1(int nod)
{
    viz[nod]=1;
    for(auto i: g[nod])
        if(!viz[i]) dfs1(i);
    st.push(nod);
}

void dfs2(int nod)
{
    comp[k].push_back(nod);
    viz[nod]=1;
    for(auto i: revg[nod])
        if(!viz[i]) dfs2(i);
}

void Kosaraju()
{
    for(int i=1; i<=n; ++i)
        if(!viz[i]) dfs1(i);

    for(int i=1; i<=n; ++i)
        viz[i]=0;

    while (!st.empty())
    {
        int v=st.top();
        st.pop();
        if(viz[v]==0)
        {
            dfs2(v);
            k++;
        }
    }
}

void afisare()
{
    fout<<k<<endl;
    for(int i=0; i<k; ++i)
    {
        for(auto j: comp[i])
            fout<<j<<" ";
        fout<<endl;
    }

}

int main()
{
    fin>>n>>m;
    int x, y;
    for(int i=1; i<=m; ++i)
    {
        fin>>x>>y;
        g[x].push_back(y);
        revg[y].push_back(x);
    }
    Kosaraju();
    afisare();
    return 0;
}