Pagini recente » Cod sursa (job #305488) | Cod sursa (job #2489557) | Cod sursa (job #1415531) | Cod sursa (job #1219397) | Cod sursa (job #1322012)
using namespace std;
#include <vector>
#include <stack>
#include <cstring>
#define NMAX 50001
class Graph
{
private:
int size; bool seen[NMAX],t[NMAX];
vector <int> AdList[NMAX];
public:
vector <int> sol;
void setSize(int n)
{
size=n;
memset(seen,0,sizeof(seen));
memset(t,0,sizeof(t));
}
void addEdge(int i, int j)
{
AdList[i].push_back(j);
t[j]=1;
}
void dfs(int node)
{
seen[node]=1;
for(int i=0;i<AdList[node].size();i++)
if(!seen[AdList[node][i]])
dfs(AdList[node][i]);
sol.push_back(node);
}
vector <int> toposort()
{
int i;
for(i=1;i<=size;i++)
if(!t[i])
dfs(i);
int n=sol.size(),aux;
for(i=0;i<n/2;i++)
{
aux=sol[i];
sol[i]=sol[n-i-1];
sol[n-i-1]=aux;
}
return sol;
}
}G;
#include <fstream>
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector <int> v;
int main()
{
int n,m,x,y;
f>>n>>m;
G.setSize(n);
while(m--)
{
f>>x>>y;
G.addEdge(x,y);
}
v=G.toposort();
for(int i=0;i<v.size();i++)
g<<v[i]<<' ';
}