Pagini recente » Cod sursa (job #608978) | Cod sursa (job #753790) | Statistici Braban Ovidiu (ovidiu055) | Cod sursa (job #1130845) | Cod sursa (job #2334683)
#include <bits/stdc++.h>
using namespace std;
const int nmax=50005;
vector <int> g[nmax];
vector <int> g_r[nmax];
vector <int> rasp;
vector <int> aux;
bool visited[nmax];
bool modif;
struct numere
{
int priority;
int val;
}v[nmax];
void dfs_pri(int start_node)
{
visited[start_node]=true;
v[start_node].priority++;
for(int i=0;i<g[start_node].size();i++)
{
if(visited[g[start_node][i]]==false)
{
dfs_pri(g[start_node][i]);
v[start_node].priority+=v[g[start_node][i]].priority;
}
}
}
bool cmp(numere a, numere b)
{
if(a.priority==b.priority)
return a.val<b.val;
return a.priority<b.priority;
}
void dfs_afis(int start_node)
{
visited[start_node]=true;
aux.push_back(start_node);
for(int i=0;i<g_r[start_node].size();i++)
if(visited[g_r[start_node][i]]==false)
dfs_afis(g_r[start_node][i]);
}
int main()
{
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for(int i=1;i<=m;i++)
{
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g_r[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
v[i].val=i;
if(visited[i]==false)
dfs_pri(i);
}
sort(v+1, v+n+1, cmp);
memset(visited, false, sizeof(visited));
for(int i=1;i<=n;i++)
{
if(visited[v[i].val]==false)
{
dfs_afis(v[i].val);
reverse(aux.begin(), aux.end());
for(int i=0;i<aux.size();i++)
rasp.push_back(aux[i]);
aux.clear();
}
}
for(int i=0;i<n;i++)
printf("%d ", rasp[i]);
printf("\n");
return 0;
}