Cod sursa(job #1303483)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 28 decembrie 2014 00:17:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 100001
using namespace std;
FILE *f=fopen("ctc.in","r"),*g=fopen("ctc.out","w");
int postord[nmax],viz[nmax],n,lg,t;
vector <int> l[nmax],lt[nmax],r[nmax];
void df(int k)
{
    int i,x;
    viz[k]=1;
    for(i=0;i<l[k].size();i++)
    {
        x=l[k][i];
        if(!viz[x])
            df(x);
    }
    postord[++lg]=k;
}
void dft(int k)
{
    int i,x;

    r[t].push_back(k);
    viz[k]=0;
    for(i=0;i<lt[k].size();i++)
    {
        x=lt[k][i];
        if(viz[x])
                dft(x);
    }

}
int main()
{
    int i,j,m,x,y;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        l[x].push_back(y);
        lt[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
        df(i);
    for(i=n;i>=1;i--)
        if(viz[postord[i]])
    {
        ++t;
        dft(postord[i]);
    }
    fprintf(g,"%d\n",t);
    for(i=1;i<=t;i++)
    {
        for(j=0;j<r[i].size();j++)
            fprintf(g,"%d ",r[i][j]);
        fprintf(g,"\n");
    }
    return 0;
}