Cod sursa(job #2528592)

Utilizator mirceaisherebina mircea mirceaishere Data 22 ianuarie 2020 10:42:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, i, j, k, x, y, componente, niv[100010], low[100010];
stack <int> s;
bitset <100010> IS;
vector<int> a[100010], sol[100010];


void dfs(int nod){
    k++;
    niv[nod]=k;
    low[nod]=k;
    s.push(nod);
    IS[nod]=1;
    for(int i=0; i<a[nod].size(); i++) {
        int vecin=a[nod][i];
        if(niv[vecin]==0) {
            dfs(vecin);
            low[nod]=min(low[nod], low[vecin]);
        }else{
            if(IS[vecin]!=0){
                low[nod]=min(low[nod], low[vecin]);
            }
        }

    }
    if(niv[nod]==low[nod]){
        componente++;
        int aux;
        do{
            aux=s.top();
            s.pop();
            IS[aux] = 0;
            sol[componente].push_back(aux);
        }while(aux!=nod);
    }
}

int main() {
    fin>>n>>m;
    for (i=1; i<=m; i++) {
        fin>>x>>y;
        a[x].push_back(y);
    }
    for (i=1;i<=n;i++){
        if (niv[i]==0){
            dfs(i);
        }
    }

    fout<<componente<<"\n";
    for (i=1; i<=componente; i++){
        for (j=0; j<sol[i].size(); j++){
            fout<<sol[i][j]<<" ";
        }
        fout<<"\n";
    }
}