Pagini recente » Cod sursa (job #1085913) | Cod sursa (job #995811) | Cod sursa (job #2410555) | Cod sursa (job #2916286) | Cod sursa (job #2610511)
#include <bits/stdc++.h>
using namespace std;
const int kNmax = 100005;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
int n;
int m;
vector<int> adj[kNmax];
// Intern degree of the nodes
vector<int> inDegree;
void read_input() {
ifstream fin("ortaret.in");
fin >> n >> m;
inDegree = vector<int>(n + 1, 0);
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
++inDegree[y]; // edge entering y
}
fin.close();
}
void computeDFS(int node, vector<int> &visited, vector<int> &topsort) {
// Mark node as visited
visited[node] = 1;
// Recursively visit every node
for (auto &it : adj[node]) {
if (!visited[it]) {
computeDFS(it, visited, topsort);
}
}
// End of topsort
topsort.push_back(node);
}
vector<int> computeBFS() {
// Declare queue
queue<int> q;
// Initialize topsort
vector<int> topsort;
// Add to queue every 0 inDegree node
for (int i = 1; i <= n; ++i) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// Do the BFS
while (!q.empty()) {
// Remove first node from queue
int node = q.front();
q.pop();
// Add used element to the topsort
topsort.push_back(node);
// Parse the neighbours
for (auto &it : adj[node]) {
// Decrease the size of inDegree for it
// to simulate the deletion of the edge
--inDegree[it];
// If the node has an inDegree of 0
// add it to the queue
if (inDegree[it] == 0) {
q.push(it);
}
}
}
// Verify that the topsort traversal is valid
// meaning that there are no more edges in the graph
// as in inDegree[i] == 0, i = 1..n
bool isValid = true;
for (int i = 1; i <= n; ++i) {
if (inDegree[i] > 0) {
isValid = false;
return {};
}
}
return topsort;
}
vector<int> get_result() {
vector<int> topsort;
topsort = computeBFS();
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();
}
};
// Please always keep this simple main function!
int main() {
// Allocate a Task object on heap in order to be able to
// declare huge static-allocated data structures inside the class.
Task *task = new Task();
task->solve();
delete task;
return 0;
}