Cod sursa(job #3344306)

Utilizator RaresAnghelAnghel Rares Mihai RaresAnghel Data 1 martie 2026 20:17:26
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.63 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector<int>adj[101];
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[101];
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;
}