Pagini recente » Cod sursa (job #2541789) | Cod sursa (job #1622504) | Cod sursa (job #1931070) | Cod sursa (job #2091567) | Cod sursa (job #3167154)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
void canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> graf[50001];
vector<int> dependencies[50001];
queue<int> st;
bool fr[50001] = {false};
bool visited[50001] = {false};
for (int i = 0; i < prerequisites.size(); i++)
{
fr[prerequisites[i][0]] = true;
graf[prerequisites[i][1]].push_back(prerequisites[i][0]);
dependencies[prerequisites[i][0]].push_back(prerequisites[i][1]);
}
for (int i = 0; i < numCourses; i++)
{
if (!fr[i])
{
st.push(i);
visited[i] = true;
}
}
int currentNode;
bool ok;
while (!st.empty())
{
currentNode = st.front();
st.pop();
fout << currentNode + 1 << ' ';
for (int i = 0; i < graf[currentNode].size(); i++)
{
if (visited[graf[currentNode][i]] == false)
{
ok = true;
for (int j = 0; j < dependencies[graf[currentNode][i]].size(); j++)
{
if (visited[dependencies[graf[currentNode][i]][j]] == 0)
{
ok = false;
break;
}
}
if (ok)
{
visited[graf[currentNode][i]] = true;
st.push(graf[currentNode][i]);
}
}
}
}
}
int n, m, x, y;
int main()
{
vector<vector<int>> dep;
fin >> n >> m;
for (int i = 0; i < m; i++)
{
fin >> x >> y;
vector<int> aux;
aux.push_back(y - 1);
aux.push_back(x - 1);
dep.push_back(aux);
}
canFinish(n, dep);
return 0;
}