Cod sursa(job #3230206)

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

#define NMAX 100000


#define NOTVISITED 0
#define VISITING 1
#define VISITED 2


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

    // std::cout << prefix << "----(" << source + 1 << ")----\n";
    // std::cout << prefix << "--------(" << source + 1 << ")\n";

    for (auto neigh : adj[source]) {
        if (vis[neigh] == NOTVISITED) {
        // if (found[neigh] == -1) {
            tarjan(neigh, adj, timestamp, found, low_link, vis, sccs, prefix + "  ");
            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]);
        // }
        // else if (vis[neigh] == VISITING || vis[neigh] == VISITED) {
        else {
            low_link[source] = std::min(low_link[source], found[neigh]);
        }
    }

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

        // std::cout << prefix << "stack - ";

        do {
            // std::cout << sccs[0].back() + 1 << ' ';
            sccs.back().push_back(sccs[0].back());
            sccs[0].pop_back();
        } while (sccs.back().back() != source);

        // std::cout << "\n";
    }

    vis[source] = VISITED;

    // std::cout << prefix << "--------\n";
}

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], vis[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)
        vis[i] = NOTVISITED;
        // found[i] = -1;

    sccs.push_back({});

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

    sccs.erase(sccs.begin());


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

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

        fout << '\n';
    }

    // for (int i = 0; i < n; ++i)
    //     fout << low_link[i] << ' ';

    // fout << '\n';


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

    return 0;
}