Cod sursa(job #2931655)

Utilizator vlanderovlad rosu vlandero Data 31 octombrie 2022 18:12:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.2 kb
/*
Aplic algoritmul lui Kosaraju, folosind proprietatea unei componente tare conexe ca daca inversez muchiile din aceasta, va ramane componenta tare conexa.
Parcurg graful initial cu un dfs si adaug un nod in stiva dupa ce parcurg toti vecinii lui.
Parcurg graful cu muchiile inversate cu un dfs din nodurile pop-uite din stiva, pe rand, si actualizez evident vectorul de vizitare.
Este esential sa introduc in stiva nodul DUPA ce parcurg toti vecinii lui, ca apoi cand parcurg dfs pe graful cu muchiile inversate sa incep din el, si sa vad daca pot ajunge inapoi prin muchiile prin care am ajuns la nodul respectiv

O(n+m)
*/

#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;
}