Cod sursa(job #1327722)

Utilizator japjappedulapPotra Vlad japjappedulap Data 27 ianuarie 2015 00:28:45
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
using namespace std;

#define NSIZE 100003
#define INF 1<<27

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

int N, M, Index[NSIZE], L[NSIZE], idx;
bool B[NSIZE];

vector <int> G[NSIZE], C;
vector < vector <int> > SCC;
stack <int> S;

void Tarjan(int x);

int main()
{
    is >> N >> M;
    for (int i = 1, a, b; i <= M; ++i)
    {
        is >> a >> b;
        G[a].push_back(b);
    }
    for (int i = 1; i <= N; ++i)
        if (Index[i] == 0)
            Tarjan(i);
    os << SCC.size() << '\n';
    for (int i = 0; i < SCC.size(); ++i, os << '\n')
        for (const int& j : SCC[i])
            os << j << ' ';
    is.close();
    os.close();
}

void Tarjan(int x)
{
    Index[x] = L[x] = ++idx;
    S.push(x), B[x] = 1;
    for (const int& i : G[x])
        if (Index[i] == 0)
        {
            Tarjan(i);
            L[x] = min(L[x], L[i]);
        }
        else
            if (B[i] == 1)
                L[x] = min(L[x], L[i]);
    if (Index[x] == L[x])
    {
        C.clear();
        int node;
        do
        {
            node = S.top(); S.pop();
            C.push_back(node); B[node] = 0;
        }
        while (!S.empty() && node != x);
        SCC.push_back(C);
        C.clear();
    }
};