Cod sursa(job #952368)

Utilizator andrei0610Andrei Constantinescu andrei0610 Data 23 mai 2013 10:26:38
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
//
//  ctc.cpp
//  Componente Tare Conexe
//
//  Created by Andrei Constantinescu on 23.05.2013.
//  Copyright (c) 2013 Andrei Constantinescu. All rights reserved.
//

#include <fstream>
#include <vector>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

#define NMAX 100

int n,m;

vector <int> grf[NMAX],grft[NMAX],con[NMAX];

int st[NMAX],k=0,nrcon;

bool viz[NMAX];

void df(int nod) {
    viz[nod]=1;
    for(int i=0;i<grf[nod].size();i++)
        if(!viz[grf[nod][i]]) df(grf[nod][i]);
    st[k]=nod;
    k++;
}

void dft(int nod) {
    viz[nod]=0;
    con[nrcon].push_back(nod);
    for(int i=0;i<grft[nod].size();i++)
        if(viz[grft[nod][i]]) dft(grft[nod][i]);
}

int main() {
    f>>n>>m;
    for(int i=1; i<=m; i++) {
        int a, b;
        f>>a>>b;
        grf[a].push_back(b);
        grft[b].push_back(a);
    }
    
    for(int i=1;i<=n;i++)
        if(!viz[i]) df(i);
    
    nrcon=0;
    for(int i=n-1;i>=0;i--)
        if(viz[st[i]]) {
            dft(st[i]);
            nrcon++;
        }
    
    g<<nrcon;
    g<<"\n";
    
    for(int i=0;i<nrcon;i++) {
        for(int j=0;j<con[i].size();j++)
            g<<con[i][j]<<" ";
        g<<"\n";
    }
}