Cod sursa(job #2928880)

Utilizator bogdanputineluBogdan Putinelu bogdanputinelu Data 24 octombrie 2022 01:40:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n,m,compConexe,ind;
vector<vector<int>> adiacenta,componente;
stack<int> noduri;
vector<bool> stiva;
vector<int> index,lowlink;
ifstream f("ctc.in");
ofstream g("ctc.out");
void strongconnect(int nod){
    lowlink[nod]=index[nod]=ind;
    ind++;
    noduri.push(nod);
    stiva[nod]=true;
    for(int i = 0; i<adiacenta[nod].size();++i){
        if(index[adiacenta[nod][i]]==-1){
            strongconnect(adiacenta[nod][i]);
            lowlink[nod]=min(lowlink[nod],lowlink[adiacenta[nod][i]]);
        }
        else
            if(stiva[adiacenta[nod][i]]){
                lowlink[nod]=min(lowlink[nod],index[adiacenta[nod][i]]);
            }
    }
    if(lowlink[nod]==index[nod]){
        compConexe++;
        int aux;
        do{
            aux=noduri.top();
            componente[compConexe].push_back(aux);
            stiva[aux]=false;
            noduri.pop();
        }while(aux!=nod);
    }
}
int main(){
    f>>n>>m;
    int a,b;
    adiacenta.resize(n+1);
    componente.resize(n+1);
    lowlink.resize(n+1);
    stiva.resize(n+1,false);
    index.resize(n+1,-1);
    for (int i = 0; i < m; ++i) {
        f>>a>>b;
        adiacenta[a].push_back(b);
    }
    for(int i=1;i<=n;++i){
        if(index[i]==-1)
            strongconnect(i);
    }
    g<<compConexe<<'\n';
    for(int i=1;i<=compConexe;++i){
        for (int j = 0; j < componente[i].size(); ++j) {
            g<< componente[i][j]<<' ';
        }
        g<<'\n';
    }
    return 0;
}