Cod sursa(job #1366375)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 28 februarie 2015 23:42:52
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

fstream f("ctc.in",ios::in);
fstream g("ctc.out",ios::out);

const int nmax = 100010;

vector <int> a[nmax], tc[nmax];

stack <int> s;

int n, m , i, x, y, nr, nrc, viz[nmax], niv[nmax], low[nmax], inStack[nmax];

void citire()
{
    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> x >> y;
        a[x].push_back(y);
    }
}

void DFS(int nc)
{
    niv[nc] = nr;
    low[nc] = nr;
    nr++;
    viz[nc] = 1;
    s.push(nc);
    inStack[nc] = 1;
    for (vector <int>::iterator it = a[nc].begin(); it != a[nc].end(); ++it)
    {
        if (viz[*it])
        {
            if (niv[*it] < low[nc]) low[nc] = niv[*it];
        }
        else
        {
            DFS(*it);
            if (low[*it] < low[nc]) low[nc] = low[*it];
        }
    }
    if (low[nc] == niv[nc])
    {
        nrc++;
        do
        {
            x = s.top();
            s.pop();
            inStack[x] = 0;
            tc[nrc].push_back(x);
        } while (x != nc);
    }
}

int main()
{
    citire();
    for (i = 1; i <= n ; i++) if (!viz[i]) DFS(i);
    g << nrc << '\n';
    for (i = 1; i <= nrc; i++)
    {
        for (vector <int>::iterator it = tc[i].begin(); it != tc[i].end(); ++it) g << *it << " ";
        g << '\n';
    }
    return 0;
}