Cod sursa(job #1630444)

Utilizator StrokeSimion Valentin Stroke Data 5 martie 2016 09:12:12
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>

using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int nr,nrc,i,j,n,m,x,y,p[100001],v[100001],a[100001][30],b[100001][30],c[1000][1000];

void DFST(int x)
{
    int i;
    v[x]=0;
    ++c[nrc][0];
    c[nrc][c[nrc][0]]=x;
    for(i=1;i<=b[x][0];++i)
        if(v[b[x][i]])
            DFST(b[x][i]);
}

void DFS(int x)
{
    int i;
    v[x]=1;
    for(i=1;i<=a[x][0];++i)
        if(!v[a[x][i]])
            DFS(a[x][i]);
    p[++nr]=x;
}


int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        ++a[x][0];
        ++b[y][0];
        a[x][a[x][0]]=y;
        b[y][b[y][0]]=x;
    }

    for(j=1;j<=n;++j)
        if(!v[j])
            DFS(j);

    for(j=n;j>0;--j)
        if(v[p[j]])
        {
            ++nrc;
            DFST(p[j]);

        }

    g<<nrc<<'\n';
    for(i=1;i<=nrc;++i)
    {
        for(j=1;j<=c[i][0];++j)
            g<<c[i][j]<<" ";
        g<<'\n';
    }


    return 0;
}