Cod sursa(job #2117755)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 29 ianuarie 2018 16:07:09
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb

#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

vector<int> G[NMAX], Gt[NMAX], L, Sol[NMAX];
int N, M, viz[NMAX], k, c[NMAX], NrComp,x,y;

void Read();
void Solve();
void Write();

void visit(int node);                                           //Topological sort
void create(int node, int component);

int main()
{
    Read();
    Solve();
    Write();
}

void Solve()
{
    for(int node=1; node<=N; node++)
        visit(node);

    while(!L.empty())
    {
        if(c[L.back()] == 0)
            create(L.back(), ++NrComp);
        L.pop_back();
    }
}
void visit(int node)
{
    if(viz[node])
        return;

    viz[node]=1;
    for(int i=0; i < G[node].size(); ++i)
            visit(G[node][i]);
    L.push_back(node);
}
void create(int node, int component)
{
    c[node] = component;
    Sol[component].push_back(node);
    for(int i=0; i < Gt[node].size(); ++i) {
        int neigh = Gt[node][i];
        if(!c[neigh])
            create(neigh, component);
    }
}
void Write()
{
    fout<<NrComp<<'\n';
    for(int i=1; i<=NrComp; i++) {
        for(int j=0; j < Sol[i].size(); j++)
            fout<<Sol[i][j]<<' ';
        fout<<'\n';
    }
}
void Read()
{

    fin>>n>>m;
    for(int i=1; i<=M; i++) {
            fin>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
}