Cod sursa(job #2929035)

Utilizator anamaria_panait.10Panait Ana-Maria anamaria_panait.10 Data 24 octombrie 2022 14:44:49
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

vector<int> adj[100000], componente[100000];
int ids[100000], low[100000];
stack<int> stiva;
bool peStiva[100000];
int id = 1;
int ctc = 0;


void dfs(int nod_curent){
    stiva.push(nod_curent);
    peStiva[nod_curent] = true;
    ids[nod_curent] = low[nod_curent] = id++;
    for(int i = 0; i < adj[nod_curent].size(); i++){
        int vecin = adj[nod_curent][i];
        if(ids[vecin] == 0)
            dfs(vecin);
        if(peStiva[vecin] == true)
            low[nod_curent] = min(low[nod_curent], low[vecin]);
    }

    if(ids[nod_curent] == low[nod_curent]){
        int nod;
        ctc++;
        do{
            nod = stiva.top();
            low[nod] = ids[nod_curent];
            peStiva[nod] = false;
            stiva.pop();
            componente[ctc].push_back(nod);
        } while(nod != nod_curent);
    }
}

int main()
{
    int n, m, x, y;
    in >> n >> m;
    for(int i = 0; i < m; i++){
        in >> x >> y;
        adj[x].push_back(y);
    }


    for(int i = 1; i <= n; i++){
        if(ids[i] == 0)
            dfs(i);
    }

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