Cod sursa(job #2961033)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 5 ianuarie 2023 16:30:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include<bits/stdc++.h>



using namespace std;

const int maxN = (1e5)+5;


vector<int> v[maxN];


int niv[maxN],low[maxN];

int st[maxN],vf;

bool inStack[maxN];

vector<int> C[maxN];

int ctc;
int lvl;

void dfs(int nod)
{
    lvl++;
    niv[nod] = lvl;
    low[nod] = lvl;

    st[++vf] = nod;


    inStack[nod] = 1;

    for(auto it:v[nod])
    {
        if(!niv[it])
        {
            dfs(it);
            low[nod] = min(low[nod],low[it]);
        }
            else
        if(inStack[it])
        {
            low[nod] = min(low[nod],low[it]);
        }
    }

    if(low[nod]==niv[nod])
    {

        ctc++;

        while(vf>0 && st[vf]!=nod)
        {
            C[ctc].push_back(st[vf]);
            inStack[st[vf]] = 0;
            vf--;
        }

        C[ctc].push_back(st[vf]);
        inStack[st[vf]] = 0;
        vf--;
    }
}


int main()
{

    ifstream fin("ctc.in");
    ofstream fout("ctc.out");


    int n,m;

    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y;

        fin>>x>>y;

        v[x].push_back(y);

    }

    for(int i=1;i<=n;i++)
    {
        if(!niv[i])
            dfs(i);
    }

    fout<<ctc<<'\n';


    for(int i=1;i<=ctc;i++)
    {
        for(auto it:C[i])
            fout<<it<<' ';
        fout<<'\n';
    }
    return 0;
}