Pagini recente » Cod sursa (job #2074277) | Cod sursa (job #292449) | Cod sursa (job #969873) | Cod sursa (job #2414225) | Cod sursa (job #472511)
Cod sursa(job #472511)
#include<fstream>
#include<vector>
#include<list>
#include<stack>
#define NMAX 100005
using namespace std;
long n,m,vizitat[NMAX];
stack<long> S;
struct nod
{
long varf;
//long cost;
nod(){}
nod(long nvarf) : varf(nvarf){}
};
vector<list<nod>> G;
void dfs(long x)
{
list<nod>::iterator itr;
for(itr=G[x].begin(); itr!=G[x].end(); itr++)
{
if(vizitat[(*itr).varf]==0)
{
vizitat[(*itr).varf]=1;
dfs((*itr).varf);
}
}
S.push(x);
}
void topologicalSort()
{
long i;
for(i=1;i<=n;i++)
if(vizitat[i]==0)
{
vizitat[i]=1;
dfs(i);
}
}
int main()
{
fstream fin,fout;
long i,x,y,c;
fin.open("dag.in",ios::in);
fout.open("dag.out",ios::out);
list<nod> lista;
fin>>n>>m;
for(i=0;i<=n;i++)
G.push_back(lista);
for(i=0;i<m;i++)
{
fin>>x>>y;
G[x].push_back(nod(y));
}
topologicalSort();
while(!S.empty())
{
fout<<S.top()<<" ";
S.pop();
}
fin.close();
fout.close();
return 0;
}