Cod sursa(job #2925294)

Utilizator vlanderovlad rosu vlandero Data 13 octombrie 2022 21:07:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n,m,current;
vector<vector<int>> graph;
vector<vector<int>> reversedGraph;
vector<vector<int>> solution;
vector<bool> viz;
stack<int> s;

void initializeViz(){
    for(int i=1;i<=n;++i)
        viz[i]=false;
}

void dfs(int node){
    for(int i=0;i<graph[node].size();++i){
        if(!viz[graph[node][i]]){
            viz[graph[node][i]]=true;
            dfs(graph[node][i]);
        }
    }
    s.push(node);
}

void reverseDfs(int node){
    solution[current].push_back(node);
    viz[node]=true;
    for(int i=0;i<reversedGraph[node].size();++i){
        if(!viz[reversedGraph[node][i]]){

            reverseDfs(reversedGraph[node][i]);
        }
    }
}

int main()
{
    int i,a,b,top;
    cin>>n>>m;
    graph.resize(n+1);
    reversedGraph.resize(n+1);
    viz.resize(n+1);
    for(i=0;i<m;++i){
        cin>>a>>b;
        graph[a].push_back(b);
        reversedGraph[b].push_back(a);
    }
    initializeViz();
    for(i=1;i<=n;++i){
        if(!viz[i]){
            dfs(i);
        }
    }
    initializeViz();
    while(!s.empty()){
        top=s.top();
        s.pop();
        if(!viz[top]){
            solution.push_back({});
            reverseDfs(top);
            current++;
        }
    }
    cout<<current<<'\n';
    for(i=0;i<current;++i){
        for(int j=0;j<solution[i].size();++j){
            cout<<solution[i][j]<<' ';
        }
        cout<<'\n';
    }

    return 0;
}