Cod sursa(job #2758100)

Utilizator MoarcascosminMoarcas Cosmin Moarcascosmin Data 8 iunie 2021 17:02:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <queue>

using namespace std;

int n, m, vizitat[100005], nr;

stack<int> stiva;
vector<int> vecini1[100005], vecini2[100005], solutie[100005];

void Citire()
{
    ifstream f("ctc.in");

    int nod1, nod2;

    f >> n >> m;

    for(int i = 0; i < m; i++)
    {
        f >> nod1 >> nod2;

        vecini1[nod1].push_back(nod2);
        vecini2[nod2].push_back(nod1);
    }
}

void Dfs(int varf)
{
    vizitat[varf] = 1;
    for(int i = 0; i < vecini1[varf].size(); i++)
        if(!vizitat[vecini1[varf][i]])
            Dfs(vecini1[varf][i]);
    stiva.push(varf);
}

void Bfs(int varf)
{
    queue<int> coada;

    coada.push(varf);
    vizitat[varf] = 1;

    while(!coada.empty())
    {
        int nod = coada.front();
        solutie[nr].push_back(nod);
        coada.pop();
        for(int i = 0; i < vecini2[nod].size(); i++)
            if(!vizitat[vecini2[nod][i]])
            {
                vizitat[vecini2[nod][i]] = 1;
                coada.push(vecini2[nod][i]);
            }
    }
}

void SortareTopologica()
{
    for(int i = 1; i <= n; i++)
        if(!vizitat[i])
            Dfs(i);
}

void ResetareVizitat()
{
    for(int i = 1; i <= n; i++)
        vizitat[i] = 0;
}

void DeterminareComponente()
{
    ResetareVizitat();
    while(!stiva.empty())
    {
        if(vizitat[stiva.top()])
            stiva.pop();
        else
        {
            Bfs(stiva.top());
            nr++;
            stiva.pop();
        }
    }
}

void Afisare()
{
    ofstream g("ctc.out");

    g << nr << '\n';

    for(int i = 0; i < nr; i++)
    {
        for(int j = 0; j < solutie[i].size(); j++)
            g << solutie[i][j] << ' ';
        g << '\n';
    }
}

int main()
{
    Citire();
    SortareTopologica();
    DeterminareComponente();
    Afisare();

    return 0;
}