Cod sursa(job #1249987)

Utilizator Andrei_TirpescuAndrei Tirpescu Andrei_Tirpescu Data 27 octombrie 2014 18:35:02
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#define NMAX 101

using namespace std;

ifstream fin("graf.in");

ofstream fout("graf.out");

int n, m, vfi;
int A[NMAX][NMAX], At[NMAX][NMAX];
bool M[NMAX],M2[NMAX], uz[NMAX];
int R[NMAX][NMAX];

void init();
void DFS(int);
void DFSt(int);

int main(){
    init();
    int i, j, ok, nr = 1, lg = 0;
    //DFS(1);
    for(i = 1; i<=n; ++i){
        DFS(i);
        DFSt(i);
        ok = 0; lg = 0;
        for(j =1; j<=n; ++j)
            if(M[j] == M2[j] && M[j] && !uz[j]){
                     ok = 1;
                     R[nr][++lg] = j;
                     uz[j] = 1;ok = 1;
            }
        if(ok){
            R[nr][0] = lg;
            ++nr;
        }
    }
    fout<<nr-1<<'\n';
    for(i = 1; i<= n; ++i){
        for(j = 1; j<= R[i][0]; ++j)fout<<R[i][j]<<" ";
        fout<<'\n';
    }

    return 0;
}

void init(){
    int x, y, i;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        A[x][++A[x][0]]=y;
        At[y][++At[y][0]]=x;
    }
}


void DFS(int k){
    int i;
    M[k] = 1;
    for(i = 1; i<= A[k][0]; ++i)
        if(!M[A[k][i]]) DFS(A[k][i]);
}

void DFSt(int k){
    int i;
    M2[k] = 1;
    for(i = 1; i<=At[k][0]; ++i)
        if(!M2[At[k][i]])DFSt(At[k][i]);
}