Cod sursa(job #1468642)

Utilizator vladttturcuman vlad vladtt Data 6 august 2015 16:29:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 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,s;

int niv[100050],stiva[100050];

bool instack[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]),instack[stiva[i]]=false;
    tot=poz-1;
}

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



    int poz=++tot;

    stiva[poz]=nod;

    instack[nod]=1;

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

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

            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);

    }


    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;
}