Cod sursa(job #892542)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 26 februarie 2013 10:28:38
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int dim = 100004;
int N, M, NB, NR, low[dim], niv[dim];
vector <int> V[dim], R[dim];
stack <int> S;

void cit ()
{
    fi >> N >> M;
    for (int i = 1, x, y; i <= M; i++)
    {
        fi >> x >> y;
        V[x].push_back (y);
        //V[y].push_back (x);
    }
}

void dfs (int n, int t)
{
    low[n] = niv[n] = ++NR;
    S.push (n);
    for (int i = 0, f; i < V[n].size(); i++)
    {
        f = V[n][i];
        if (niv[f] == 0)
        {
            dfs (f, n);
            low[n] = min (low[n], low[f]);
        }
        else
        {
            low[n] = min (low[n], niv[f]);
        }
    }

    if (niv[n] == low[n])
    {
        int f = n - 1;
        NB++;
        while (f != n)
        {
            f = S.top ();
            S.pop ();
            R[NB].push_back (f);
        }
    }
}

void afi ()
{
    int i, j;
    fo << NB << '\n';
    for (i = 1; i <= NB; i++)
    {
        for (j = 0; j < R[i].size(); j++)
        {
            fo << R[i][j] << ' ';
        }
        fo << '\n';
    }

}

int main ()
{
    cit ();
    for (int i = 1; i <= N; i++)
    {
        if (low[i] == 0)
        {
            dfs (i, 0);
        }
    }
    afi ();
    return 0;
}