Cod sursa(job #1468630)

Utilizator vladttturcuman vlad vladtt Data 6 august 2015 16:03:05
Problema Componente tare conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>


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

int tot,n,m,i,j,x,y,tot2;

int niv[100050],stiva[100050];

vector<int> v[100050],bi[100050];

void _cut(int poz)
{
    tot2++;
    for(int i=poz; i<=tot; i++)
        bi[tot2].push_back(stiva[i]);
    tot=poz-1;
}

int  dfs(int ant,int nod,int s)
{
    niv[nod]=s;

    int poz=++tot;

    stiva[poz]=nod;


    for(int i=0; i<v[nod].size(); i++)
    {
        int b=v[nod][i];

        if(niv[b]!=0)
        {
            niv[nod]= niv[nod] > niv[b] ? niv[b] : niv[nod];
        }
        else
        {
            int x=dfs(nod,b,s+1);

            niv[nod] = niv[nod] > x ? x : niv[nod];

        }
    }

    if(niv[nod]==s)
        _cut(poz);

    return niv[nod];

}


int main()
{

    fin>>n>>m;

    for(i=1; i<=m; i++)
    {
        fin>>x>>y;

        v[x].push_back(y);
    }

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

    }


    fout<<tot2<<'\n';

    for(i=1; i<=tot2; i++)
    {
        for(j=0; j<bi[i].size(); j++)
            fout<<bi[i][j]<<' ';
        fout<<'\n';

    }

    return 0;
}