Cod sursa(job #3325737)

Utilizator g.vladGociu Vlad g.vlad Data 26 noiembrie 2025 11:12:19
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb

#include <fstream>
#include <cstring>
#include <utility>
#include <vector>

using std::vector;

std::ifstream in("ctc.in");
std::ofstream out("ctc.out");

struct node_t {
    vector<unsigned> dependents;
    vector<unsigned> dependecies;
};

void dfs1(node_t* graph, bool* found, vector<unsigned>& order, unsigned at) {
    found[at] = true;
    order.push_back(at);
    for(unsigned const& dep : graph[at].dependents) {
        if(found[dep]) continue;
        dfs1(graph, found, order, dep);
    }
}

void dfs2(node_t* graph, bool* found, vector<unsigned>& cluster, unsigned at) {
    found[at] = true;
    cluster.push_back(at);
    for(unsigned const& dep : graph[at].dependecies) {
        if(found[dep]) continue;
        dfs2(graph, found, cluster, dep);
    }
}

int main() {
    unsigned nodes, edges;
    node_t graph[100001];

    in >> nodes >> edges;

    for(unsigned a, b, edge = 0; edge < edges; edge += 1) {
        in >> a >> b;
        graph[a].dependents.push_back(b);
        graph[b].dependecies.push_back(a);
    }

    vector<unsigned> order;

    bool found[100001];

    std::memset(found, 0x00, 100001);
    for(unsigned node = 1; node <= nodes; node += 1) {
        if(found[node]) continue;
        dfs1(graph, found, order, node);
    }

    vector<vector<unsigned>> clusters;

    std::memset(found, 0x00, 100001);
    for(unsigned const& elem : order) {
        if(found[elem]) continue;
        vector<unsigned> cluster;
        dfs2(graph, found, cluster, elem);
        clusters.push_back(std::move(cluster));
    }

    out << clusters.size() << '\n';

    for(vector<unsigned> const& cluster : clusters) {
        for(unsigned const& elem : cluster) {
            out << elem << ' ';
        }
        out << '\n';
    }

    return 0;
}