Cod sursa(job #2928750)

Utilizator JovialJokerFlorea George JovialJoker Data 23 octombrie 2022 19:56:41
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<vector<int>> la(100001);
vector<vector<int>> transpusa(100001);
vector<bool> viz(100001);
vector<int> stack;
int index = 0;
map<int, vector<int>> compConexe;

void DFS(int node){
    viz[node] = true;

    for(auto iter: la[node]){
        if(!viz[iter]){
            DFS(iter);
        }
    }

    stack.push_back(node);
}

void dfsTransp(int node){
    viz[node] = true;

    for(auto iter: transpusa[node]){
        if(!viz[iter]){
            dfsTransp(iter);
        }
    }

    compConexe[index].push_back(node);
}

int main() {
    f>>n>>m;
    for(int i = 0; i < m; i++){
        int v1, v2;
        f>>v1>>v2;
        la[v1].push_back(v2);
        transpusa[v2].push_back(v1);
    }

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

    viz = vector<bool> (n+1, false);

    for(vector<int>:: reverse_iterator iter = stack.rbegin(); iter != stack.rend(); iter++){
        if(!viz[*iter]){
            dfsTransp(*iter);
            index++;
        }
    }

    index--;
    g<<index<<endl;
    for(auto iter: compConexe){
        if(iter.first != index){
            for(auto iter2: iter.second){
                g<<iter2<<" ";
            }
            g<<endl;
        }
    }

    return 0;
}