Cod sursa(job #1669987)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 31 martie 2016 12:36:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;

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

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

void visit(int node);                                           //Topological sort
void create_Strongly_Conn_Component(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_Strongly_Conn_Component(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_Strongly_Conn_Component(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_Strongly_Conn_Component(neigh, component);
    }
}
void Write()
{
    cout<<NrComp<<'\n';
    for(int i=1; i<=NrComp; i++) {
        for(int j=0; j < Sol[i].size(); j++)
            cout<<Sol[i][j]<<' ';
        cout<<'\n';
    }
}
void Read()
{
    freopen("ctc.in","rt",stdin);
    freopen("ctc.out","wt",stdout);
    int x, y;
    scanf("%d%d",&N, &M);
    for(int i=1; i<=M; i++) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
}