Cod sursa(job #1090210)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 22 ianuarie 2014 14:35:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int MAXN = 100010;

vector <int> GrafT[MAXN], Graf[MAXN];
vector < vector <int> > Sol;
vector <int> now;
int St[MAXN];
bool Viz[MAXN];

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

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

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

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

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

int main()
{
    int N, M, a, b, i;

    in >> N >> M;
    while (M --){
        in >> a >> b;
        GrafT[b].push_back (a);
        Graf[a].push_back (b);
    }

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

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

    for (i = N; i; 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 ++, out << "\n")
        for (auto it : Sol[i])
            out << it << " ";

    return 0;
}