Cod sursa(job #1414687)

Utilizator rangerChihai Mihai ranger Data 2 aprilie 2015 21:27:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
#include<vector>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int Nmax=100003;
#define pb push_back
int N, i, x,y, M, cp;
vector< int > g[Nmax], gt[Nmax], Cp[Nmax], V(Nmax,0), order;

void dfs(int v)
{
    V[v]=1;
    for (int i=0;i<g[v].size();i++)
        if (!V[g[v][i]]) dfs(g[v][i]);
    order.pb(v);
}
void dfs_(int v)
{
    V[v]=1;
    Cp[cp].pb(v);
    for (int i=0;i<gt[v].size();i++)
        if (!V[gt[v][i]]) dfs_(gt[v][i]);
}

int main()
{
    cin >> N >> M;
    while (M--){
        cin>>x>>y;
        g[x].pb(y);
        gt[y].pb(x);
    }
    for (i=1;i<=N;i++)
        if (!V[i]) dfs(i);
    for (i=1;i<=N;i++) V[i]=0;

    for (i=N-1;i>=0;i--)
    if (!V[order[i]]){
        dfs_(order[i]);cp++;
    }
    cout<<cp<<'\n';
    for (i=0;i<cp;i++){
        for (int j=0;j<Cp[i].size();j++)cout<<Cp[i][j]<<' ';
        cout<<'\n';
    }
    return 0;
}