Cod sursa(job #3371500)

Utilizator fulop.krisztian.zsoltfulop.krisztian.zsolt fulop.krisztian.zsolt Data 30 octombrie 2026 16:39:43
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 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++) {
        elerheto(graph,nodes,i);
        for (int j : volt) {
            elerheto_m[i][j]=1;
        }
        volt.clear();
    }

    /*for (vector<int> x : elerheto_m) {
        for (int y : x) {
            cout<<y<<" ";
        }
        cout<<endl;
    }*/

    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 (vector<int> conex : tare_conex) {
        for (int node : conex) {
            fout << node << " ";
        }
        fout << endl;
    }
    return 0;
}