Cod sursa(job #3230207)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 19 mai 2024 21:52:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

#define NMAX 100000



void tarjan(int source, std::vector<int> adj[],
            int &timestamp, int found[], int low_link[],
            std::vector<std::vector<int>> &sccs)
{
    ++timestamp;
    found[source] = timestamp;
    low_link[source] = timestamp;
    sccs[0].push_back(source);


    for (auto neigh : adj[source]) {
        if (found[neigh] == -1) {
            tarjan(neigh, adj, timestamp, found, low_link, sccs);
            low_link[source] = std::min(low_link[source], low_link[neigh]);
        } else if (std::find(sccs[0].begin(), sccs[0].end(), neigh) != sccs[0].end()) {
            low_link[source] = std::min(low_link[source], found[neigh]);
        }
    }
    

    if (low_link[source] == found[source]) {
        sccs.push_back({});

        do {
            sccs.back().push_back(sccs[0].back());
            sccs[0].pop_back();
        } while (sccs.back().back() != source);
    }
}

int main()
{
    std::ifstream fin("ctc.in");
    std::ofstream fout("ctc.out");

    int n, m;
    std::vector<int> adj[NMAX];
    int timestamp = 0, found[NMAX], low_link[NMAX];
    std::vector<std::vector<int>> sccs;


    fin >> n >> m;

    for (int v, w, i = 0; i < m; ++i) {
        fin >> v >> w;
        adj[v - 1].push_back(w - 1);
    }


    for (int i = 0; i < n; ++i)
        found[i] = -1;

    sccs.push_back({});

    for (int i = 0; i < n; ++i)
        if (found[i] == -1)
            tarjan(i, adj, timestamp, found, low_link, sccs);

    sccs.erase(sccs.begin());


    fout << sccs.size() << '\n';

    for (auto scc : sccs) {
        for (auto node : scc)
            fout << node + 1 << ' ';

        fout << '\n';
    }


    fin.close();
    fout.close();

    return 0;
}