Cod sursa(job #1447161)

Utilizator FlowstaticBejan Irina Flowstatic Data 3 iunie 2015 19:46:28
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 100005
using namespace std;
FILE* fin=fopen("ctc.in","r");
FILE* fout=fopen("ctc.out","w");

vector< int > G[NMAX];
vector< int > GT[NMAX];

int N, M;
bool viz[NMAX];
int post[NMAX];
int k;
int nr;
int ap[NMAX];

void CitireListeAdiacenta();
void DFS1(int x);
void DFS2(int x);
void Afisare();

int main()
{

    CitireListeAdiacenta();

    //PARCURGERE 1
    int i;
    for( i = 1; i <= N; i++)
        if( !viz[i] )
                DFS1(i);

    memset(viz,0,sizeof(viz));
    //PARCURGERE 2
    for( i = N; i >= 1; i--)
        if( !viz[post[i]] )
                {
                    nr++;
                    DFS2(post[i]);
                }

    Afisare();
    return 0;
}

void CitireListeAdiacenta()
{
    int i, x, y;
    fscanf(fin,"%d %d",&N,&M);

    for(i = 1; i <= M ; i++)
    {
        fscanf(fin,"%d %d",&x,&y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void DFS1(int x)
{
    int i;
    viz[x] = 1;
    for( i = 0; i < G[x].size(); i++)
         if( viz[G[x][i]] == 0 )
               DFS1(G[x][i]);
    post[++k] = x;
}

void DFS2(int x)
{
    int i;
    viz[x] = 1;
    ap[x] = nr;
    for( i = 0; i < GT[x].size(); i++)
         if( viz[GT[x][i]] == 0 )
               DFS2(GT[x][i]);
}

void Afisare()
{
    fprintf(fout,"%d\n",nr);
    int i,j;
    for(i = 1; i <= nr; i++)
    {
        for( j = 1; j <= N; j++)
            if(ap[j] == i)
                fprintf(fout,"%d ",j);
        fprintf(fout,"\n");
    }
}