Cod sursa(job #2832576)

Utilizator enestianEne Sebastian enestian Data 13 ianuarie 2022 22:17:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.53 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int N;
int M;
int start;
vector<vector<int>> vecini;

void citire_graf() {
    f >> N;
    f >> M;
    int nod1, nod2;
    vecini.resize(N + 1);
    for (int i = 0; i < M; i++) {
        f >> nod1 >> nod2;
        vecini[nod1].push_back(nod2);
    }
}



void DFS_CTC(vector<bool>& inStiva, int fiu, vector<int>& nivel, vector<int>& low, stack<int>& stack, vector<vector<int>>& compConexe, int& nrCC, int &dist) {

    nivel[fiu] = low[fiu] = dist;
    dist=dist+1;
    stack.push(fiu);
    inStiva[fiu] = true;
    
    int i;
    for (i = 0; i < vecini[fiu].size(); i++)
    {   
        if (nivel[vecini[fiu][i]] == -1) {//nevizitat
            DFS_CTC(inStiva, vecini[fiu][i], nivel, low, stack, compConexe, nrCC, dist);
            low[fiu] = min(low[fiu], low[vecini[fiu][i]]);
        }
        else if (inStiva[vecini[fiu][i]] == true) {//daca e in stiva
            low[fiu] = min(low[fiu], nivel[vecini[fiu][i]]);
        }        
    }
    if (low[fiu]== nivel[fiu]) {//cand nivel fiu ajunge  egal cu low de fiu,avem nod radacina
        //incepem componenta tare conexa       
        int node = stack.top();
        stack.pop();
        inStiva[node] = false;
        compConexe[nrCC].push_back(node);

        while (node != fiu)			
        {
            node = stack.top();
            stack.pop();
            inStiva[node] = false;
            compConexe[nrCC].push_back(node);
        }        
        nrCC++;
    }
}

void CTC_init_si_print() {
    vector<bool> inStiva(N+1 , false);
    vector<int> nivel(N+1);//vector de nivele 
    vector<int> low(N+1);//vector de low level pentru fiecare nod
    stack<int> stack;  //stiva cu nodurile vizitate
    vector<vector<int>> compConexe;
    compConexe.resize(N+1);
    int nrCC = 0;
    int dist = 0;

    // Initialize disc and low, and stackMember arrays
    for (int i = 1; i <= N; i++)
    {
        nivel[i] = -1;
        low[i] = -1;
        inStiva[i] = false;
    }


    for (int i = 1; i <= N; i++)
        if (nivel[i] == -1)
            DFS_CTC(inStiva, i, nivel, low, stack, compConexe, nrCC, dist);
    g << nrCC << '\n';
    for (int i = 0; i < nrCC; i++) {
        for (int j = 0; j < compConexe[i].size(); j++)
            g << compConexe[i][j] << " ";
        g << '\n';
    }
}

int main()
{
   
    citire_graf();
    
    CTC_init_si_print();
	return 0;
}