Cod sursa(job #2925289)

Utilizator ralucarRogoza Raluca ralucar Data 13 octombrie 2022 18:49:46
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#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(100001);
vector<vector<int>> ctc;
vector <int> v, index(1000), pozmin(1000), viz(1000);
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;
    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;
}