Cod sursa(job #1090226)

Utilizator EduardGeorgescuGeorgescu Eduard EduardGeorgescu Data 22 ianuarie 2014 14:43:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>

#define MAXN 100010

using namespace std;

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

vector<int>G[MAXN];
vector<int>Gt[MAXN];
vector<int>now;
vector<vector<int>>Sol;

bool Viz[MAXN];
int St[MAXN];

void TopSort( int nod){
    Viz[nod] = 1;

    for ( auto it : Gt[nod])
        if ( !Viz[it])
        TopSort(it);

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

void DFS(int nod)
{
    now.push_back(nod);
    Viz[nod]=1;

    for ( auto it : G[nod] )
        if ( !Viz[it])
            DFS(it);
}

int main()
{
    int N,M;

    in >> N >> M;

    int i,x,y;

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

    for ( i = 1 ; i <= N ; i ++)
        if ( !Viz[i])
            TopSort (i);

    memset(Viz,0,sizeof(Viz));

    for ( i = N ; i >= 1 ; i --)
        if ( !Viz[St[i]] )
        {
            DFS (St[i]);
            Sol.push_back(now);
            now.clear();
        }

    int Sz = Sol.size();
    out << Sz << "\n";

    for ( i = 0 ; i < Sz ; i ++)
    {
        for ( auto it : Sol[i])
            out << it << " ";
        out << "\n";
    }


    return 0;
}