Cod sursa(job #2814340)

Utilizator IoanaLiviaPopescu15Ioana Livia IoanaLiviaPopescu15 Data 7 decembrie 2021 22:52:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 100001

using namespace std;

bool visited[N];
	
//ifstream fin("dfs.in");
//ofstream fout("dfs.out");
	
// ifstream fin("bfs.in");
// ofstream fout("bfs.out");
	
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
	
class Graph {
	
public:
	vector <int> adiacenta[N];
    vector <int> solution;
    int n_g, m_g;
    void addEdge_neorientat(int h, int t);
    void addEdge_orientat(int h, int t);
    void BFS_mininum_distances(int root);
	void DFS(int vf);
};
	
 
	
void Graph::addEdge_neorientat(int h,int t)
{
     adiacenta[h].push_back(t);
     adiacenta[t].push_back(h);
}

void Graph::addEdge_orientat(int h,int t)
{
     adiacenta[h].push_back(t);
}
 
	
void Graph::DFS(int vf)
{
	visited[vf] = true;
	
	for(int i = 0; i < adiacenta[vf].size(); ++i)
		if (!visited[adiacenta[vf][i]])
			DFS(adiacenta[vf][i]);
    
    solution.push_back(vf);
	
}


void Graph::BFS_mininum_distances(int root)
{
        vector<int> d(n_g + 1, -1);
        queue<int> q;
	
        d[root] = 0;
        q.push(root);
	
        while (!q.empty()) {
            int current = q.front();
            q.pop();
 
            for (auto &index : adiacenta[current]) {
                if (d[index] == -1)
                {
                    d[index] = d[current] + 1;
                    q.push(index);
                }
            }

        }
	
        for (int i = 1; i <= n_g; ++i) {
            fout << d[i] << ' ';
        }
}

	
int main()
{
	
	int n, m, n1, n2, conexe = 0, s = 2;
	//pb 2 fin >> n >> m >> s;

    fin>>n>>m;
	
	Graph g;

    g.n_g = n;
    g.m_g = m;
	
    for (int i = 1; i <= m; i++)
	{
        fin >> n1 >> n2;
        g.addEdge_orientat(n1,n2);
    }
	
    //tema 1: pb 1 : DFS : comp conexe
	// for(int i = 1; i <= n; i++){
    //     if (!visited[i])
    //     {
    //        conexe += 1;
    //        g.DFS(i);
    //     }
	// }
	//fout << conexe;

    //tema 1: pb 2: BFS : min distante
    //g.BFS_mininum_distances(s);

    for (int i = 1; i <= n; ++i)
        if (!visited[i])
            g.DFS(i);
	
 
	
    int upper_limit = g.solution.size() - 1;
	
    for (int i = upper_limit; i > -1; i--)
        fout << g.solution[i] << ' ';

	return 0;
	
}