Cod sursa(job #2928437)

Utilizator Petrica81Simion Petrica Petrica81 Data 22 octombrie 2022 22:00:58
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<vector<int>> graf,componente;
vector<int> index, low_index;
vector<bool> on_stack;
stack<int> s;
int n, m, dex = 1;

void tarjan(int nod) {
    index[nod] = dex;
    low_index[nod] = dex;
    dex++;
    s.push(nod);
    on_stack[nod] = true;
    for (int i = 0; i < graf[nod].size(); i++){
        if(index[graf[nod][i]] == 0) {
            tarjan(graf[nod][i]);
            low_index[nod] = min(low_index[nod],low_index[graf[nod][i]]);
        }
        if(on_stack[graf[nod][i]])
            low_index[nod] = min(low_index[nod],low_index[graf[nod][i]]);
    }
    if(low_index[nod] == index[nod]){
        componente.push_back({});
        int x,y = componente.size()-1;
        do{
            x = s.top();
            componente[y].push_back(x);
            on_stack[x] = false;
            s.pop();
        }while (nod != x);
    }
}


int main() {
    in>>n>>m;
    graf.resize(n+1);
    index.resize(n+1);
    on_stack.resize(n+1);
    low_index.resize(n+1);
    for(int i = 1; i <= m; i++){
        int v1,v2;
        in>>v1>>v2;
        graf[v1].push_back(v2);
    }
    for(int i = 1; i<= n ; i++)
        if(index[i] == 0)
            tarjan(i);


    out<<componente.size()-1<<'\n';
    for(int i = 0; i < componente.size(); i++){
        for(int j = 0; j < componente[i].size(); j++)
            out<<componente[i][j]<<" ";
        out<<'\n';
    }
    return 0;
}