Cod sursa(job #2795820)

Utilizator cosmin1812Nedelcu Adrian Cosmin cosmin1812 Data 7 noiembrie 2021 00:48:34
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.43 kb
#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
using namespace std;


class Graf
{

private:

	int nr_noduri;
	int nr_muchii;
	vector<vector<int>> lista;
	

public:

	Graf(){}

	void citire_graf_dfs() {

		ifstream f("dfs.in");
		int x, y;
		f >> nr_noduri;
		f >> nr_muchii;

		lista.resize(get_nr_noduri() + 1);


		while (f >> x >> y) {

			lista[x].push_back(y);
			lista[y].push_back(x);
			
		}

		f.close();
	}


	void citire_graf_bfs() {
		

		int start;
		ifstream f("bfs.in");
		int x, y;
		f >> nr_noduri;
		f >> nr_muchii;
		f >> start;

		lista.resize(get_nr_noduri() + 1);

		while (f >> x >> y) {

			lista[x].push_back(y);
		}
	}

	int get_nr_noduri() { return nr_noduri; }
	void set_nr_noduri(int n) { nr_noduri = n; }

	int get_nr_muchii() { return nr_muchii; }
	void set_nr_muchii(int m) { nr_muchii = m; }


	void bfs(int start) {

		queue<int>coada;
		int x;

		vector<int> vizit;
		for (int i = 0; i <= nr_noduri; i++) { vizit.push_back(-1); }

		coada.push(start);
		vizit[start] = 0;

		while (!coada.empty()) {

			x = coada.front();
			coada.pop();

			for (int i = 0; i < lista[x].size(); i++) {

				if (vizit[lista[x][i]] == -1) {

					coada.push(lista[x][i]);
					vizit[lista[x][i]] = vizit[x] + 1;
				}
			}
		}

		ofstream g("bfs.out");
		for (int i = 1; i <= nr_noduri; i++) {

			g << vizit[i] << " ";
		}
		g.close();
	}

	void dfs(int start, vector<int>& vizit) {

		int v;
		stack<int>st;
		int x;

		st.push(start);
		vizit[start] = 1;

		while (!st.empty()) {

			x = st.top();
			v = 0;


			for (int i = 0; i < lista[x].size(); i++) {


				if (vizit[lista[x][i]] == 0) {

					v = lista[x][i];
					break;
				}
			}


			if (v == 0) { st.pop(); }
			else {

				st.push(v);
				vizit[v] = 1;
			}
		}
	}

	void dfs_topologic(int start, vector<int>& vizit, vector<int>& topo) {

		int v;
		stack<int>st;
		int x;

		st.push(start);
		vizit[start] = 1;

		while (!st.empty()) {

			x = st.top();
			v = 0;


			for (int i = 0; i < lista[x].size(); i++) {


				if (vizit[lista[x][i]] == 0) {

					v = lista[x][i];
					break;
				}
			}


			if (v == 0) { topo.push_back(st.top()); st.pop(); }
			else {

				st.push(v);
				vizit[v] = 1;
			}
		}
	}



	void comp_conexe() {

		citire_graf_dfs();

		vector<int> vizit;
		for (int i = 0; i <= nr_noduri ; i++) { vizit.push_back(0); }

		int count = 0;
		
		for (int i = 1; i <= nr_noduri ; i++) {

			if (vizit[i] == 0) {

				dfs(i, vizit);
				count++;
			}
			
		}

		ofstream g("dfs.out");
		g << count;
		g.close();
	}


	void citire_ST() {

		ifstream f("sortaret.in");
		int x, y;
		f >> nr_noduri;
		f >> nr_muchii;


		lista.resize(get_nr_noduri() + 1);


		while (f >> x >> y) {

			lista[x].push_back(y);

		}
		f.close();
	}

	void SortareTopologica() {

		citire_ST();

		vector<int> topo;
		vector<int> vizit;

		for (int i = 0; i <= nr_noduri; i++) { vizit.push_back(0); }

		for (int i = 1; i <= nr_noduri; i++) {

			if (vizit[i] == 0) {

				dfs_topologic(i, vizit, topo);

			}

		}

		ofstream g("sortaret.out");
		for (int i = topo.size() - 1; i >= 0; i--) {

			g << topo[i] << " ";
		}
		g.close();
	}


};

int main() {

	Graf* g = new Graf;

	g->SortareTopologica();

	return 0;
}