Cod sursa(job #2301139)

Utilizator SweetHumanAvram Gheorghe SweetHuman Data 12 decembrie 2018 18:17:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>

#include <fstream>

#include <stack>

#include <vector>



using namespace std;

ifstream fin("ctc.in");

ofstream fout("ctc.out");

stack <int> S;

int ix[100010],llx[100010],ok[100010];

int nr=0;

vector <int> G[100010];

vector <int> Sol[100010];

int n,m,index=1;

void citire()

{

    int x, y;

    fin>>n>>m;

    for(int i=1; i<=m; i++)

    {

        fin>>x>>y;

        G[x].push_back(y);

    }

}

void tarjan(int v)

{

    ix[v]=index;

    llx[v]=index;

    index++;

    S.push(v);

    ok[v]=1;

    for(auto &x:G[v])

    {

        if(ix[x]==0)

        {

            tarjan(x);

            llx[v]=min(llx[v],llx[x]);

        }

        else if(ok[x])

        {

            llx[v]=min(llx[v],ix[x]);

        }

    }

    if(llx[v]==ix[v])

    {   nr++;

        while(!S.empty()&&S.top()!=v)

        {

            Sol[nr].push_back(S.top());

            ok[S.top()]=0;

            S.pop();

        }

        if(!S.empty())

        {

            Sol[nr].push_back(S.top());

            ok[S.top()]=0;

            S.pop();

        }



    }



}



int main()

{

    citire();

    for(int i=1; i<=n; i++)

    {

        if(ix[i]==0)

            tarjan(i);

    }

    fout<<nr<<"\n";

    for(int i=1; i<=nr; i++)

    {

        for(auto &vf: Sol[i])

            fout<<vf<<" ";

        fout<<"\n";

    }



    return 0;

}