Cod sursa(job #949248)

Utilizator BitOneSAlexandru BitOne Data 12 mai 2013 22:02:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <vector>
#include <fstream>
#include <cstdlib>

using namespace std;

const int NMAX = 100011;

int idx, countStc;
bool isInStack[NMAX];
int dfsIdx[NMAX], lowIdx[NMAX];

vector<int> S;
vector<int> G[NMAX], Stc[NMAX];

inline void DFS(int x)
{
    S.push_back(x);
    isInStack[x] = true;
    dfsIdx[x] = lowIdx[x] = ++idx;

    for(auto& y : G[x])
    {
        if(!dfsIdx[y])
        {
            DFS(y);
            lowIdx[x] = min(lowIdx[x], lowIdx[y]);
        }
        else if(isInStack[y])
        {
            lowIdx[x] = min(lowIdx[x], lowIdx[y]);
        }
    }
    if(dfsIdx[x] == lowIdx[x])
    {
        int y;
        do
        {
            Stc[countStc].push_back(y = S.back()); S.pop_back();
            isInStack[y] = false;
        }while(x != y);
        ++countStc;
    }
}
int main()
{
    int N, M, x, y;
    ifstream in("ctc.in");
    ofstream out("ctc.out");

    for(in >> N >> M; M; --M)
    {
        in >> x >> y;
        G[x].push_back(y);
    }
    for(x = 1; x <= N; ++x)
    {
        if(!dfsIdx[x])
        {
            DFS(x);
        }
    }
    out << countStc << '\n';
    for(x = 0; x < countStc; ++x)
    {
        for(auto& y : Stc[x])
        {
            out << y << ' ';
        }
        out << '\n';
    }

    return EXIT_SUCCESS;
}