Pagini recente » Cod sursa (job #1017119) | Monitorul de evaluare | Atasamentele paginii Profil cristina_s | Cod sursa (job #935564) | Cod sursa (job #3344310)
#include <bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector<int>adj[50001];
vector<int>dist(101);
vector<bool>viz(101,false);
void bfs(int start)
{
queue<int>q;
viz[start]=true;
dist[start]=0;
q.push(start);
while(!q.empty())
{
int nod=q.front();
q.pop();
for(int vec:adj[nod])
{
if(!viz[vec])
{
dist[vec]=dist[nod]+1;
q.push(vec);
viz[vec]=true;
}
}
}
}
void dfs(int start)
{
viz[start]=true;
for(int vec:adj[start])
if(!viz[vec])
dfs(vec);
}
//vector<pair<int,int>>v[101];
//vector<int>dist(101)
/*void dij(int start)
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
dist[start]=0;
pq.push({0,start});
while(!pq.empty())
{
int d=pq.top().first;
int nod=pq.top().second;
if(d>dist[nod]) break;
for(int i=0;i<v[nod].size();i++)
{
int vec=v[nod][i].first;
int cost=v[nod][i].second;
if(dist[nod]+cost<dist[vec])
{
dist[vec]=dist[nod]+cost;
pq.push({dist[vec],vec});
}
}
}
}*/
unordered_map<int,int>tata;
int find(int x)
{
if(tata.find(x)==tata.end()) return x;
if(tata[x]!=x) tata[x]=find(tata[x]);
return tata[x];
}
void unite(int x,int y)
{
tata[find(x)]=find(y);
}
//vector<tuple<int,int,int>>v;
/*
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
v.push_back(make_tuple(c,a,b));
}
sort(v.begin(),v.end());
int nr=0,cost=0;
for(int i=0;i<m;i++)
{
int cost=get<0>(v[i]);
int n1=get<1>(v[i]);
int n2=get<2>(v[i]);
if(find(n1)!=find(n2)) unite(n1,n2),nr++,sum+=cost;
if(nr==n-1) break;
}
cout<<sum;
return 0;
}
*/
int n,m;
int grad[50001];
void sort_top()
{
queue<int>q;
for(int i=1;i<=n;i++)
if(grad[i]==0)q.push(i);
vector<int>sol;
while(!q.empty())
{
int nod=q.front();
q.pop();
for(int vec:adj[nod])
{
grad[vec]--;
if(grad[vec]==0) q.push(vec);
}
sol.push_back(nod);
}
for(int x:sol) g<<x<<' ';
}
int main()
{
f>>n>>m;
for(int i=0;i<m;i++)
{
int a,b;
f>>a>>b;
adj[a].push_back(b);
grad[b]++;
}
sort_top();
return 0;
}