Cod sursa(job #1117891)

Utilizator Theorytheo .c Theory Data 23 februarie 2014 20:54:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

const int NMAX = 100009;

int N; vector<int> G[NMAX], GT[NMAX]; int ord[NMAX];bool viz[NMAX];

vector<vector<int> > Conex;

int M;

void dfs(int nod) {

    viz[nod] = true;

    for(unsigned i = 0;i < G[nod].size(); ++i)
    if(viz[G[nod][i]] == false) dfs(G[nod][i]);

    ord[++ord[0]] = nod;
}


void dfs2(int nod) {

    viz[nod] = true;
    Conex[Conex.size() - 1].push_back(nod);


    for(unsigned i = 0 ;i < GT[nod].size(); ++i)
    if(viz[GT[nod][i]] == false)
        dfs2(GT[nod][i]);
}

int main() {

    fin >> N >> M;

    for(int i = 1; i <= M; ++i){

        int a, b;
        fin >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    for(int i = 1; i<= N; ++i)
        if(viz[i] == false)
            dfs(i);

    memset(viz, false, sizeof(viz));
    for(int i = N; i >= 1; --i) {

        if(viz[ord[i]] == false) {
            Conex.push_back(vector<int>(0));
            dfs2(ord[i]);
        }
    }
    fout << Conex.size() <<'\n';

    for(unsigned i = 0 ;i < Conex.size(); ++i) {
        for(unsigned j = 0 ;j < Conex[i].size(); ++j)
            fout << Conex[i][j] <<" " ;
        fout << '\n';
    }

    return 0;
}