Cod sursa(job #2852835)

Utilizator VladTZYVlad Tiganila VladTZY Data 19 februarie 2022 17:04:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <stack>

#define NMAX 100005

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n, m, x, y, ctcCounter, totalCounter;
bool viz[NMAX], onStack[NMAX];
int order[NMAX], index[NMAX];
vector <int> neighbours[NMAX], ctcNodes[NMAX];
stack <int> stck;

void DFS(int node) {

    viz[node] = true;
    totalCounter++;
    index[node] = totalCounter;
    order[node] = totalCounter;
    stck.push(node);
    onStack[node] = true;

    for (auto neighbour : neighbours[node]) {

        if (!viz[neighbour]) {

            DFS(neighbour);
            order[node] = min(order[node], order[neighbour]);

        } else if (onStack[neighbour]) {

            order[node] = min(order[node], index[neighbour]);
        }
    }

    if (order[node] == index[node]) {

        ctcCounter++;

        while (stck.top() != node) {

            ctcNodes[ctcCounter].push_back(stck.top());
            onStack[stck.top()] = false;
            stck.pop();
        }

        ctcNodes[ctcCounter].push_back(node);
        onStack[node] = false;
        stck.pop();
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> x >> y;

        neighbours[x].push_back(y);
    }

    for (int i = 1; i <= n; i++) {

        if (!viz[i])
            DFS(i);
    }

    g << ctcCounter << "\n";
    for (int i = 1; i <= ctcCounter; i++) {

        for (auto node : ctcNodes[i])
            g << node << " ";
        g << "\n";
    }

    return 0;
}