Cod sursa(job #2534872)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 31 ianuarie 2020 00:25:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

#define MAXN    100005
#define FILE    std::string("disjoint")

std::ifstream input (FILE+".in");
std::ofstream output(FILE+".out");

int N, M;
std::vector <int> ADC[MAXN];
inline void addEdge(int u, int v) {
    ADC[u].push_back(v);
}

std::stack <int> stack;
std::vector <int> cnx[MAXN];
int disc[MAXN], low[MAXN], _time, cnxCount;
bool inStack[MAXN];

void DFS(int vertex = 1) {
    stack.push(vertex);
    inStack[vertex] = true;
    disc[vertex] = low[vertex] = ++_time;
    for (auto &it:ADC[vertex]) {
        if (disc[it]) {
            if (inStack[vertex]) low[vertex] = std::min(low[vertex], low[it]);
        }
        else {
            DFS(it);
            low[vertex] = std::min(low[vertex], low[it]);
        }
    }

    if (disc[vertex] == low[vertex]) {
        while (!stack.empty() && stack.top() != vertex) {
            inStack[stack.top()] = false;
            cnx[cnxCount].push_back(stack.top());
            stack.pop();
        }
            inStack[stack.top()] = false;
            cnx[cnxCount].push_back(stack.top());
            stack.pop();
        ++ cnxCount;
    }
}

int main()
{
    input >> N >> M;
    for (int i=0, x, y; i<M; ++i)
        input >> x >> y, addEdge(x, y);

    for (int i=1; i<=N; ++i)
        if (!disc[i]) DFS(i);

    output << cnxCount << '\n';
    for (int i=0; i<cnxCount; ++i, output << '\n')
        for (auto &it:cnx[i])
            output << it << ' ';

    return 0;
}