Cod sursa(job #2927458)

Utilizator razvan1234Danciu Razvan razvan1234 Data 20 octombrie 2022 16:56:02
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

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

void constr_list(int n, int m, vector<vector<int>> &l_a, vector<vector<int>> &l_a_t)
{
    std::vector<int> t; //lista vida
    for (int j = 0; j <= n; j++) l_a.push_back(t), l_a_t.push_back(t); //imi initializez lista de liste cu n liste vide
    for (int i = 1; i <= m; i++){
        int vf1, vf2;
        fin>>vf1>>vf2;
        l_a[vf1].push_back(vf2);
        l_a_t[vf2].push_back(vf1);
    }
}

void DFS(int d, vector<int> &vizit, vector<vector<int>> list_a, stack<int> &st)
{
    vizit[d] = 1;
    for (int i = 0; i < list_a[d].size(); i++){
        if (!vizit[list_a[d][i]]){
            DFS(list_a[d][i], vizit, list_a, st);
        }
    }
    st.push(d);
}

void DFS_trans(int d, int nr, vector<int> &vizit, vector<vector<int>> &comp, vector<vector<int>> l_a_t)
{
    vizit[d] = 2;
    comp[nr].push_back(d);

    for (int i = 0; i < l_a_t[d].size(); i++){
        if(vizit[l_a_t[d][i]] == 1){
            DFS_trans(l_a_t[d][i], nr, vizit, comp, l_a_t);
        }
    }
}



int main() {
    int n,m; //noduri/muchii
    vector<vector<int>> list_adj; //lista de adiacenta pentru graful normal
    vector<vector<int>> list_adj_trans; //lista de adiacenta pentru graful transpus
    fin>>n>>m;

    vector<int> vizit; //vectorul de noduri vizitate
    for (int i = 0; i <= n; i++) vizit.push_back(0); //initializat cu 0
    stack<int> stack;//stiva in care adaugam nodurile

    constr_list(n, m, list_adj, list_adj_trans);

    for (int i = 1; i <= n; i++){
        if (!vizit[i]) DFS(i, vizit, list_adj, stack);
    }

    int nr_comp = 0;
    vector<vector<int>> componente;
    vector<int> empty;
    componente.push_back(empty);
    while(!stack.empty()){
        int nod_curent = stack.top();
        if (vizit[nod_curent] == 1){
            nr_comp++;
            componente.push_back(empty);
            DFS_trans(nod_curent, nr_comp, vizit, componente, list_adj_trans);
        }
        stack.pop();
    }
    fout<<nr_comp<<"\n";
    for (int i = 1; i <= nr_comp; i++){
        for (auto it: componente[i]){
            fout<<it<<" ";
        }
        fout<<"\n";
    }
    return 0;
}