Cod sursa(job #3230199)

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

#define NMAX 50000


#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)
{
    ++timestamp;
    found[source] = timestamp;
    low_link[source] = timestamp;
    // vis[source] = VISITING;
    // sccs.back().push_back(source);
    sccs[0].push_back(source);

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

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

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

        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----\n";
    }

    // vis[source] = VISITED;
}

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.pop_back();
    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;
}