Cod sursa(job #881779)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 18 februarie 2013 16:43:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int MAXN = 100010;

stack <int> S;
vector <int> Graf[MAXN];
vector < vector <int> > Sol;
bool Viz[MAXN];
int low[MAXN], index[MAXN];
int now;

void tarjan (int nod)
{
    int x;
    vector <int> :: iterator it;
    ++ now;
    index[nod] = now;
    low[nod] = now;
    S.push (nod);
    Viz[nod] = 1;

    for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it){
        if (index[*it] == -1){
            tarjan (*it);
            low[nod] = min (low[nod], low[*it]);
        }
        else
            if (Viz[*it])
                low[nod] = min (low[nod], index[*it]);
    }

    if (low[nod] == index[nod]){
        vector <int> CTC;

        do{
            CTC.push_back (x = S.top ());
            Viz[x] = 0;
            S.pop ();
        }while (x != nod);

        Sol.push_back (CTC);
    }
}

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

    in >> N >> M;

    for (i = 1; i <= N; i ++)
        index[i] = -1;

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

    for (i = 1; i <= N; i ++)
        if (index[i] == -1)
            tarjan (i);

    out << Sol.size () << "\n";

    for (i = 0; i < Sol.size (); i ++, out << "\n")
        for (j = 0; j < Sol[i].size (); j ++)
            out << Sol[i][j] << " ";

    return 0;
}