Cod sursa(job #3233960)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 5 iunie 2024 16:31:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>

#include <algorithm>

#include <vector>
#include <stack>
#include <unordered_set>

#define NMAX 100000

std::ifstream fin;
std::ofstream fout;


void dfs_top(int node, std::vector<int> adj[], std::unordered_set<int> &used, std::stack<int> &st)
{
    used.insert(node);

    for (auto neigh : adj[node])
        if (used.find(neigh) == used.end())
            dfs_top(neigh, adj, used, st);

    st.push(node);
}

void dfs_scc(int node, std::vector<int> adj[], std::unordered_set<int> &used, std::vector<int> &scc)
{
    scc.push_back(node);
    used.insert(node);

    for (auto neigh : adj[node])
        if (used.find(neigh) == used.end())
            dfs_scc(neigh, adj, used, scc);
}

int main()
{
    int n, m;
    std::vector<int> adj[NMAX], adjt[NMAX];
    std::unordered_set<int> used;
    std::stack<int> top_sort;
    std::vector<std::vector<int>> sccs;

    fin.open("ctc.in");
    fout.open("ctc.out");

    fin >> n >> m;

    for (int src, dest, i = 0; i < m; ++i) {
        fin >> src >> dest;

        adj[src - 1].push_back(dest - 1);
        adjt[dest - 1].push_back(src - 1);
    }


    for (int v = 0; v < n; ++v)
        if (used.find(v) == used.end())
            dfs_top(v, adj, used, top_sort);

    used.clear();

    while (!top_sort.empty()) {
        auto v = top_sort.top();
        top_sort.pop();

        if (used.find(v) == used.end()) {
            sccs.push_back({});
            dfs_scc(v, adjt, used, sccs.back());
        }
    }


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

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

        fout << '\n';
    }

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

    return 0;
}