Pagini recente » Cod sursa (job #2927420) | Cod sursa (job #1365887) | Cod sursa (job #2862742) | Cod sursa (job #1845322) | Cod sursa (job #2075875)
#include <stdio.h>
#include <stdlib.h>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;
vector<int> * citire(int *m, int *n)
{
int a,b;
FILE * fin = fopen("sortaret.in","r");
fscanf(fin,"%d %d",n,m);
vector<int> * v;
v= (vector<int> *)malloc((*n)*sizeof(vector<int>));
for(int i=0;i<*m;i++)
{
fscanf(fin,"%d %d",&a,&b);
v[a-1].push_back(b-1);
}
return v;
}
void dfs(int nod, stack <int> *stk, vector<int> * g, bitset<50010> * viz)
{
for(int i=0;i<(g[nod]).size();i++)
if((*viz)[g[nod][i]]==0)
{
(*viz)[g[nod][i]]=1;
dfs(g[nod][i],stk,g,viz);
}
(*stk).push(nod);
}
stack <int> toposort(vector<int> * g, int m, int n)
{
bitset <50010> viz;
stack <int> rez;
for(int i=0;i<n;i++)
if (viz[i]==0)
{
viz[i]=1;
dfs(i,&rez,g,&viz);
}
return rez;
}
void afisare(stack <int> * rez)
{
FILE * fout = fopen("sortaret.out","w");
while(!((*rez).empty()))
{
int t=(*rez).top();
(*rez).pop();
fprintf(fout,"%d ",t+1);
}
}
int main()
{
int m,n;
vector<int> * g = citire(&m,&n);
stack <int> rez = toposort(g,m,n);
afisare(&rez);
return 0;
}