Cod sursa(job #2935464)

Utilizator Mike07Mihai-Alexandru Militaru Mike07 Data 6 noiembrie 2022 19:08:01
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
vector<vector<int>> graph;
vector<vector<int>> graph_t;
int index;
stack <int> st;
vector<int> viz;
vector<vector<int>> comp;


void DFS_t(vector<vector<int>> graph_t, int n, int x, int index){
    viz[x]=index;
    for(int i=0;i<graph_t[x].size();i++){
        if(viz[graph_t[x][i]]==0){
            DFS_t(graph_t,n,graph_t[x][i], index);
        }
    }
    st.push(x);

}


void DFS(vector<vector<int>> graph, int n, int x){
    viz[x]=index;
    for(int i=0;i<graph[x].size();i++){
        if(viz[graph[x][i]]==0){
            DFS(graph,n,graph[x][i]);
        }
    }
    st.push(x);

}



int main() {
    index=1;
    int n,m;
    ifstream f;
    ofstream g;
    f.open("graf.in");
    g.open("graf.out");
    f>>n>>m;
    graph.resize(n+1);
    graph_t.resize(n+1);
    viz.resize(n+1);
    for(int i=0;i<m;i++){
        int x,y;
        f>>x>>y;
        graph[x].push_back(y);
        graph_t[y].push_back(x);
    }

    // Kosaraju

    for(int i=1;i<=n;i++){
        if(viz[i]==0){
            DFS(graph,n,i);
        }
    }

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

    while(st.size()){
        int x=st.top();
        st.pop();
        if(viz[x]==0){
            DFS_t(graph_t, n, x, index);
            vector<int>arr;
            for(int i=1;i<=n;i++){
                if(viz[i]==index){
                    arr.push_back(i);

                }
            }
            index+=1;
            comp.push_back(arr);

        }


    }
    g<<index-1<<"\n";
    for(auto & i : comp){
        for(int j : i){
            g<<j<<" ";
        }
        g<<"\n";
    }

    return 0;
}