Mai intai trebuie sa te autentifici.
Cod sursa(job #2797810)
Utilizator | Data | 10 noiembrie 2021 17:03:53 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.07 kb |
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
ifstream f("sortaret.in");
ofstream o("sortaret.out");
class Graph
{
vector<bool> vis;
stack<int> S;
vector<vector<int>> adjList;
int size;
public:
Graph(int n)
{
size = n + 1;
adjList.resize(size);
for (int i = 1; i <= size; i++)
vis.push_back(false);
}
void addEdge(int start, int end)
{
adjList[start].push_back(end);
}
void DFS(int node)
{
vis[node] = true;
for (auto i : adjList[node])
if (!vis[i])
DFS(i);
S.push(node);
}
void tS()
{
for (int i = 1; i < size-1; i++)
if (!vis[i])
DFS(i);
while(!S.empty())
{
o<<S.top()<<" ";
S.pop();
}
}
};
int main()
{
int n, m;
int x, y;
f >> n >> m;
Graph g(n);
for (int i = 1; i <= m; i++)
{
f >> x >> y;
g.addEdge(x, y);
}
g.tS();
return 0;
}