Cod sursa(job #1376034)

Utilizator darrenRares Buhai darren Data 5 martie 2015 15:36:48
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
vector<int> V[100002];
vector<vector<int> > COMP;
int comp[100002], ST[100002];
int D[100002], minD[100002];

void Tarjan(int x)
{
    D[x] = ++D[0];
    minD[x] = D[x];
    ST[++ST[0]] = x;

    for (auto it = V[x].begin(); it != V[x].end(); ++it)
    {
        if (!D[*it])
            Tarjan(*it);
        if (!comp[*it])
            minD[x] = min(minD[x], minD[*it]);
    }

    if (minD[x] == D[x])
    {
        COMP.push_back(vector<int>());
        comp[x] = COMP.size();

        while (true)
        {
            COMP.back().push_back(ST[ST[0]]);
            --ST[0];
            if (ST[ST[0] + 1] == x) break;
        }
    }
}

int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    fin >> N >> M;
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        fin >> nod1 >> nod2;
        V[nod1].push_back(nod2);
    }

    Tarjan(1);

    fout << COMP.size() << '\n';
    for (int i = 0; i < int(COMP.size()); ++i)
    {
        for (int j = 0; j < int(COMP[i].size()); ++j)
            fout << COMP[i][j] << ' ';
        fout << '\n';
    }

    fin.close();
    fout.close();
}