Cod sursa(job #3371503)

Utilizator fulop.krisztian.zsoltfulop.krisztian.zsolt fulop.krisztian.zsolt Data 30 octombrie 2026 16:51:37
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int nodes;
vector<int> volt;

void elerheto(const vector<vector<int>>& graph, int node_count, int current_node) {
    for (int i = 1; i <= node_count; i++) {
        if (graph[current_node][i] == 1 && find(volt.begin(), volt.end(), i) == volt.end()) {
            volt.push_back(i);
            elerheto(graph, node_count, i);
        }
    }
}

int main() {
    int margins;
    fin >> nodes >> margins;

    vector<vector<int>> graph(nodes + 1, vector<int>(nodes + 1, 0));
    for (int i = 1; i <= margins; i++) {
        int x, y;
        fin >> x >> y;
        graph[x][y] = 1;
    }

    vector<vector<int>> elerheto_m(nodes + 1, vector<int>(nodes + 1, 0));
    for (int i = 1; i <= nodes; i++) {
        volt.push_back(i);
        elerheto(graph, nodes, i);

        for (int j : volt) {
            elerheto_m[i][j] = 1;
        }
        volt.clear();
    }

    vector<vector<int>> tare_conex;
    vector<bool> visited(nodes + 1, false);

    for (int i = 1; i <= nodes; i++) {
        if (visited[i]) {
            continue;
        }
        vector<int> tare_conex_sub;
        for (int j = 1; j <= nodes; j++) {
            if (!visited[j] && elerheto_m[i][j] == 1 && elerheto_m[j][i] == 1) {
                visited[j] = true;
                tare_conex_sub.push_back(j);
            }
        }
        if (!tare_conex_sub.empty()) {
            tare_conex.push_back(tare_conex_sub);
        }
    }

    fout << tare_conex.size() << endl;
    for (const vector<int>& conex : tare_conex) {
        for (int node : conex) {
            fout << node << " ";
        }
        fout << endl;
    }

    return 0;
}