Cod sursa(job #2796471)

Utilizator bianca_voicuBianca Voicu bianca_voicu Data 8 noiembrie 2021 11:21:09
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

class Graph {
private:
    int _n, _m;
    vector<int> _list[100001];
    int viz[100001];

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void addEdges();

    void dfs_ctc(int node, vector<int> &ordine);

    void transpose();

    vector<vector<int>> ctc();
};

void Graph::addEdges() {
    int x, y, i;
    for (i = 0; i < _m; i++) {
        f >> x >> y;
        _list[x].push_back(y);
    }

}

//graful transpus
void Graph::transpose() {
    vector<int> transp_edges[_n + 1];
    int i, j;
    for (i = 1; i <= _n; i++)
        for (j = 0; j < _list[i].size(); j++)
            transp_edges[_list[i][j]].push_back(i);
    for (i = 1; i <= _n; i++) {
        _list[i] = transp_edges[i];
    }
}


void Graph::dfs_ctc(int node, vector<int> &ordine) {
    viz[node] = 1;
    for (int i = 0; i < _list[node].size(); i++) {
        if (!viz[_list[node][i]])
            dfs_ctc(_list[node][i], ordine);
    }
    //in ordine pastrez nodurile cand sunt finalizate de dfs
    ordine.push_back(node);
}

vector<vector<int>> Graph::ctc() {
    vector<vector<int>> ans;

    vector<int> ordine;
    for (int i = 1; i <= _n; i++){
        if (!viz[i]) {
            dfs_ctc(i, ordine);
        }
    }
    //inversez ordinea
    reverse(ordine.begin(), ordine.end());

    //fac graful transpus
    transpose();

    //resetez vectorul de vizitari
    for (int i = 1; i <= _n; i++)
        viz[i] = 0;

    //fac dfs pentru elemente din ordine (cele inversate)
    for (int i = 0; i < _n; i++) {
        if (!viz[ordine[i]]) {
            vector<int> v;
            dfs_ctc(ordine[i], v);
            ans.push_back(v);
        }
    }

    return ans;
}


int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.addEdges();


    vector<vector<int>> ans = gr.ctc();

    cout << ans.size() << '\n';

    for (int i = 0; i < ans.size(); i++) {
        for (int j = 0; j < ans[i].size(); j++)
            g << ans[i][j] << " ";
        g << '\n';
    }

    f.close();
    g.close();
    return 0;
}