Cod sursa(job #1138609)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 10 martie 2014 12:28:26
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>

using namespace std;

fstream f("ctc.in",ios::in);
fstream g("ctc.out",ios::out);

const long nmax=100005;

vector <long> a[nmax];
stack <long> s;
vector <long> tc[nmax];

long n,m,i,x,y,nrc,ind[nmax],link[nmax],index;
int viz[nmax],stiva[nmax];

void citire()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x].push_back(y);
    }
}

void nod(long nc)
{
    long nc1;
    ind[nc]=index;
    link[nc]=index;
    index++;
    viz[nc]=1;
    stiva[nc]=1;
    s.push(nc);
    for (vector<long>::iterator it=a[nc].begin();it!=a[nc].end();++it)
        if (!viz[*it])
        {
            nod(*it);
            if (link[nc]>link[*it]) link[nc]=link[*it];
        }
        else if (stiva[*it])
        {
            if (link[nc]>ind[*it]) link[nc]=ind[*it];
        }
    if (ind[nc]==link[nc])
    {
        nrc++;
        do
        {
            nc1=s.top();
            s.pop();
            stiva[nc1]=0;
            tc[nrc].push_back(nc1);
        }
        while (nc1!=nc);
    }
}

void rezolvare()
{
    memset(viz,0,sizeof(viz));
    memset(stiva,0,sizeof(stiva));
    index=1;
    nrc=0;
    for(i=1;i<=n;i++) if (!viz[i]) nod(i);
}

void afisare()
{
    g<<nrc<<'\n';
    for (i=1;i<=nrc;i++)
    {
        for (vector<long>::iterator it=tc[i].begin();it!=tc[i].end();++it) g<<*it<<" ";
        g<<'\n';
    }
}
int main()
{
    citire();
    rezolvare();
    afisare();
    f.close();g.close();
    return 0;
}