Cod sursa(job #2879783)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 28 martie 2022 23:10:21
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

void dfs(vector <vector<int>> & vecini, bool viz[], vector <int> & rez, int start)
{
    for (auto i : vecini[start])
        if (viz[i-1])
            continue;
        else
        {
            viz[i-1] = true;
            dfs(vecini, viz, rez, i-1);
        }
    rez.push_back(start+1);

}
int noduri, muchii, i, j;
bool viz[50001];

int main()
{
    fin >> noduri >> muchii;
    vector <vector<int>> vecini;
    vecini.assign(noduri, {});
    while (muchii)
    {
        fin >> i >> j;
        vecini[i-1].push_back(j);
        muchii--;
    }
    for (i = 0; i <noduri; i++)
    {
        if (vecini[i].size())
        {
            sort(vecini[i].begin(), vecini[i].end());
            for (auto j = vecini[i].end()-1; j > vecini[i].begin(); j--)
                if (*j == *(j-1))
                    vecini[i].erase(j);
        }
    }
/*
    for (i = 0; i <noduri; i++)
    {
        fout << i + 1 << ' ';
        for (auto j : vecini[i])
            fout << j << ' ';
        fout <<'\n';
    }*/
    vector <int> rez;
    for (i = 0; i < noduri; i++)
    {
        if (viz[i] == false)
        {
            viz[i] = true;
            dfs(vecini, viz, rez, i);
        }
    }
    for (auto i = noduri-1; i >= 0; i--)
        fout << rez[i] << ' ';
    return 0;
}