Cod sursa(job #3274126)

Utilizator ShAwDoRneYNacu Gabriel ShAwDoRneY Data 5 februarie 2025 13:37:58
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

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

void DFS1(int node, vector<bool> &isVisited, vector<int> &topSort, vector<vector<int>> &graph) {

    isVisited[node] = true;

    for(auto neighbor : graph[node]) {
        if(!isVisited[neighbor])
            DFS1(neighbor, isVisited, topSort, graph);
    }

    topSort.push_back(node);

}

void DFS2(int node, int parent, vector<int> &rep, vector<bool> &isVisited, vector<set<int>> &components, vector<vector<int>> &rgraph) {

    isVisited[node] = true;
    rep[node] = parent;
    components[parent].insert(node);

    for(auto neighbor : rgraph[node]) {
        if(!isVisited[neighbor])
            DFS2(neighbor, parent, rep, isVisited, components, rgraph);
    }


}

int main() {

    int noNodes, noEdges;
    fin >> noNodes >> noEdges;

    vector<vector<int>> graph(noNodes+1, vector<int>());
    vector<vector<int>> rgraph(noNodes+1, vector<int>());
    vector<set<int>> components(noNodes+1, set<int>());

    for(int i=1; i<=noEdges; i++) {
        int firstNode, secondNode;
        fin >> firstNode >> secondNode;
        graph[firstNode].push_back(secondNode);
        rgraph[secondNode].push_back(firstNode);
    }

    vector<int> topSort;
    vector<bool> isVisited(noNodes+1, false);

    for(int i=1; i<=noNodes; i++) {
        if(!isVisited[i])
            DFS1(i, isVisited, topSort, graph);
    }

    

    reverse(topSort.begin(), topSort.end());
    fill(isVisited.begin(), isVisited.end(), false);

    vector<int> rep(noNodes+1, -1);
    int compTari = 1;

    for(auto node : topSort) {
        if(!isVisited[node]) {
            DFS2(node, compTari++, rep, isVisited, components, rgraph);
        }
    }

    fout << compTari-1 << '\n';

    for(int i=1; i<compTari; i++) {
        for(auto node : components[i])
            fout << node << ' ';
        fout << '\n';
    }


    return 0;
}