Cod sursa(job #2195472)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 16 aprilie 2018 14:42:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int kNmax = 100005, ALB = 0, GRI = 1, NEGRU = 2;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	vector<int> adj[kNmax];
    vector<int> ind;
	void read_input() {
		ifstream fin("sortaret.in");
		fin >> n >> m;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
		}
		fin.close();
	}
	void sortaret(vector<int> &result) {
        ind.resize(n + 1, 0);
		for(int i = 1; i <= n; ++i)
            for(unsigned j = 0; j < adj[i].size(); ++j)
                ++ind[ adj[i][j] ];
        queue<int> q;
        for(int i = 1; i <= n; ++i) {
            if(ind[i] == 0) {
                q.push(i);
            }
        }
        while(!q.empty()) {
            int u = q.front();
            result.push_back(u);
            q.pop();
            for(unsigned i = 0; i < adj[u].size(); ++i) {
                int v = adj[u][i];
                --ind[v];
                if(ind[v] == 0) {
                    q.push(v);
                }
            }
        }
	}
	vector<int> get_result() {
		/*
		TODO: Faceti sortarea topologica a grafului stocat cu liste de
		adiacenta in adj.
		*******
		ATENTIE: nodurile sunt indexate de la 1 la n.
		*******
		*/

		vector<int> topsort;
		sortaret(topsort);

		return topsort;
	}

	void print_output(vector<int> result) {
		ofstream fout("sortaret.out");
		for (int i = 0; i < int(result.size()); i++) {
			fout << result[i] << ' ';
		}
		fout << '\n';
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}