Cod sursa(job #2927742)

Utilizator MoarcascosminMoarcas Cosmin Moarcascosmin Data 21 octombrie 2022 11:47:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

int n, m, numarComponente;
vector<vector<int>> vecini;
vector<vector<int>> vecini2;
vector<vector<int>> componenta(100001);
stack<int> ordine;
bool vizitat[100001];
bool vizitat2[100001];

void read()
{
    ifstream f("ctc.in");
    
    f >> n >> m;
    
    int nod1, nod2;

    vecini.resize(n + 1);
    vecini2.resize(n + 1);

    for(int i = 0; i < m; i++)
    {
        f >> nod1 >> nod2;
        vecini[nod1].push_back(nod2);
        vecini2[nod2].push_back(nod1);
    }
}

void dfs(int nod)
{
    vizitat[nod] = true;

    for(auto vecin : vecini[nod])
        if(!vizitat[vecin])     
            dfs(vecin);

    ordine.push(nod);
}

void creareOrdine()
{
    for(int nod = 1; nod <= n; nod++)
        if(!vizitat[nod])
            dfs(nod);
}

void dfsComponente(int nod)
{
    vizitat2[nod] = true;
    componenta[numarComponente].push_back(nod);

    for(auto vecin : vecini2[nod])
        if(!vizitat2[vecin])
            dfsComponente(vecin);
}

void schimbareMuchii()
{
    vector<vector<int>> veciniAux;

    veciniAux.resize(n + 1);

    for(int nod = 1; nod <= n; nod++)
        for(auto vecin : vecini[nod])
            veciniAux[vecin].push_back(nod);
    vecini.clear();
    vecini = veciniAux;
}

void determinareComponente()
{
    int nod;
    componenta.resize(n + 1);


    while(!ordine.empty())
    {
        nod = ordine.top();
        ordine.pop();


        if(!vizitat2[nod])
        {  
            numarComponente++;
            dfsComponente(nod);
        }
    }
}

void afisareComponente()
{
    ofstream g("ctc.out");
    g << numarComponente << '\n';
    for(int i = 1; i <= numarComponente; i++)
    {           
        for(auto nod : componenta[i])
            g << nod << ' ';
        g << '\n';
    }

}

int main()
{
    read();
    creareOrdine();
    // schimbareMuchii();
    determinareComponente();
    afisareComponente();

    return 0;
}