Cod sursa(job #2298343)

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

#define MAXN 100005

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);
        Seen[Vertex] = 0;
        do {
            CTC[NCTC].push_back(Stack.top());
            Seen[Stack.top()] = 0;
            Stack.pop();
        }   while (Stack.top() != Vertex);
        Stack.pop();
        ++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;
}