Cod sursa(job #2927739)

Utilizator MoarcascosminMoarcas Cosmin Moarcascosmin Data 21 octombrie 2022 11:35:23
Problema Componente tare conexe Scor 60
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<int> componenta;
stack<int> ordine;
bool vizitat[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)
{
    componenta[nod] = numarComponente;

    for(auto vecin : vecini2[nod])
        if(!componenta[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(!componenta[nod])
        {  
            numarComponente++;
            dfsComponente(nod);
        }
    }
}

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

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

    return 0;
}