Cod sursa(job #2926485)

Utilizator ralucarRogoza Raluca ralucar Data 17 octombrie 2022 20:39:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
//complexitate: O(n+m)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

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

int n, m, poz=0;
vector<vector<int>> lista_adiacenta;
vector<vector<int>> ctc;
vector <int> v, index, pozmin, viz;
stack <int> stiva;

void tarjan(int x){
    stiva.push(x);
    index[x]=poz;
    pozmin[x]=poz;
    poz++;
    viz[x]=1;
    for(auto i: lista_adiacenta[x]){
        if(index[i]==-1){
            tarjan(i);
            pozmin[x]=min(pozmin[i], pozmin[x]);
        }
        else if(viz[i]==1){
            pozmin[x]=min(pozmin[i], pozmin[x]);
        }
    }
    if(index[x]==pozmin[x]){
        int p;
        do{
            p=stiva.top();
            stiva.pop();
            viz[p]=0;
            v.push_back(p);
        }while(p!=x);
        ctc.push_back(v);
        v.clear();
    }
}

int main()
{
    int x,y;
    fin>>n>>m;
    lista_adiacenta.resize(n+1);
    index.resize(n+1,-1);
    pozmin.resize(n+1,0);
    viz.resize(n+1,0);
//    for(int i = 1; i <= n; i++)
//        index[i] = -1;
//  index.assign(n, -1);
    for(int i=1; i<=m; i++){
        fin>>x>>y;
        lista_adiacenta[x].push_back(y);
    }
    for(int i=1; i<=n; i++){
        if(index[i]==-1)
            tarjan(i);
    }
    fout<<ctc.size()<<'\n';
    for(auto i1=0; i1<ctc.size(); i1++){
        for(auto i2: ctc[i1])
            fout<<i2<<" ";
        fout<<'\n';
    }
    return 0;
}