Cod sursa(job #2298347)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 8 decembrie 2018 01:17:49
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

#define MAXN 200005

int N, M;
std::vector <int> ADC[MAXN];

inline void AddEdge(int x, int y) {
    ADC[x].push_back(y);
}

int Disc[MAXN], Low[MAXN],
    Pasi;
bool Seen[MAXN];
std::stack <int> Stack;

int NCTC;
std::vector <int> CTC[MAXN];

void Tarjan(int Vertex) {
    Disc[Vertex] = Low[Vertex] = ++Pasi;
    Stack.push(Vertex);
    Seen[Vertex] = 1;

    for (auto Vecin:ADC[Vertex]) {
        if (!Disc[Vecin])
            Tarjan(Vecin),
            Low[Vertex] = std::min(Low[Vertex], Low[Vecin]);
        if (Seen[Vecin])
            Low[Vertex] = std::min(Low[Vertex], Low[Vecin]);
    }

    if (Disc[Vertex] == Low[Vertex]) {
        CTC[NCTC].push_back(Vertex);

        int Top;
        do {
            Top = Stack.top();
            Stack.pop();
            Seen[Top] = 0;
            CTC[NCTC].push_back(Top);
        }   while (Top != Vertex);

        ++NCTC;
    }
}

std::ifstream In("ctc.in");
std::ofstream Out("ctc.out");

void Citire() {
    In >> N >> M;
    for (int i=0, x, y; i<M; ++i)
        In >> x >> y, AddEdge(x, y);
}

void Rezolvare() {
    for (int i=1; i<=N; ++i)
        if (!Disc[i])
            Tarjan(i);

    Out << NCTC << '\n';
    for (int i=0, j; i<NCTC; ++i, Out << '\n')
        for (j=0; j<CTC[i].size(); ++j)
            Out << CTC[i][j] << ' ' ;
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}