Cod sursa(job #2154091)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 6 martie 2018 18:23:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,viz[nmax],nrcomp,x,y,c[nmax];
vector < int > Sol[nmax],Gt[nmax],G[nmax],L;

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);
    }
}
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 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 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';
     }
}
int main()
{
    read();
    solve();
    write();

    return 0;
}