Cod sursa(job #2798091)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 10 noiembrie 2021 21:42:20
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

vector <long> G[50005];
deque <long> S;
long N;
bool V[50001];
bool visited[50001];

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

class Graph {
public:

	vector <int> adiacenta[50001];
	deque <long> dq;
    void addEdge(int h, int t);
	void DFS(int vf);
	void ShowSolution();

};

void Graph::addEdge(int h,int t)
{
     adiacenta[h].push_back(t);
     adiacenta[t].push_back(h);
}

void Graph::DFS(int vf)
{
	visited[vf] = true;
	for(long i = 0; i < adiacenta[vf].size(); ++i)
		if (!visited[adiacenta[vf][i]])
			DFS(adiacenta[vf][i]);
    dq.push_front(vf);
}

void Graph::ShowSolution()
{
    for (long i=0; i < dq.size (); i++)
    {
        fout << dq[i] << " ";
    }

}

void Type ()
{
    for (unsigned long i=0; i < S.size (); i++)
    {
        fout << S[i] << " ";
    }

    fout << "\n";

}


/*
void DFS (long X)
{
    unsigned long i;
    V[X]=true;
    for (i=0; i<G[X].size (); i++)
    {
        if (V[G[X][i]]==false)
        {
            DFS(G[X][i]);
        }
    }
    S.push_front (X);
}*/



int main()
{
    long i, M, X, Y;
    fin >> N >> M;

    Graph g;
    for (i=0; i<M; i++)
    {
        fin >> X >> Y;
       // G[X].push_back (Y);
        g.addEdge(X,Y);

    }

    for (i=1; i<=N; i++)
    {
        if (visited[i]==false)
        {
           // DFS(i);
            g.DFS(i);
        }
    }

   // Type ();
    g.ShowSolution();
    return 0;

}