Cod sursa(job #2352905)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 23 februarie 2019 18:55:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

#define MAXN 100005

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

inline void AddEdge(int X, int Y) {
    ADC[X].push_back(Y);
}

std::stack <int> S;
bool InStack[MAXN];
int Time, Discovery[MAXN], Lowlink[MAXN];
void Tarjan(int Vertex) {
    Discovery[Vertex] = Lowlink[Vertex] = ++Time;
    S.push(Vertex);
    InStack[Vertex] = 1;

    for (auto Edge:ADC[Vertex])
        if (!Discovery[Edge])
            Tarjan(Edge),
            Lowlink[Vertex] = std::min(Lowlink[Vertex], Lowlink[Edge]);
        else if (InStack[Edge])
            Lowlink[Vertex] = std::min(Lowlink[Vertex], Lowlink[Edge]);

    if (Discovery[Vertex] == Lowlink[Vertex]) {
        int Top;
        ++ CTCSize;
        do {
            Top = S.top();
            S.pop();
            InStack[Top] = 0;
            CTC[CTCSize].push_back(Top);
        }   while (Top != Vertex);
        std::sort(CTC[CTCSize].begin(), CTC[CTCSize].end());
    }
}

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

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y; i<=M; ++i)
        In >> X >> Y, AddEdge(X, Y);
}

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

    Out << CTCSize << '\n';
    for (int i=1; i<=CTCSize; ++i, Out << '\n')
        for (auto Vertex:CTC[i])
            Out << Vertex << ' ' ;
}

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

    return 0;
}