Cod sursa(job #2376472)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 8 martie 2019 15:51:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

#define MAXN 100005

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

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

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

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

    if (Discovery[Vertex] == Lowlink[Vertex]) {
        ++ StrongSize;
        while (!Stack.empty() && Stack.top() != Vertex)
            Strong[StrongSize].push_back(Stack.top()), InStack[Stack.top()] = 0, Stack.pop();
        InStack[Vertex] = 0, Stack.pop();
        Strong[StrongSize].push_back(Vertex);
        std::sort(Strong[StrongSize].begin(), Strong[StrongSize].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])
            DFS(i);

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

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

    return 0;
}