Cod sursa(job #2921261)

Utilizator gabriela.stanStan Luciana-Gabriela gabriela.stan Data 29 august 2022 18:51:08
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <cstdio>
	
#include <cstring>
	
#include <vector>
	
using namespace std;
	
 
	
#define MAXN 50100
	
#define pb push_back
	
 
	
int N, M, deg[MAXN], Q[MAXN]; vector<int> G[MAXN];
	
 
	
// deg[x] = gradul exterior al nodului x
	
// folosesc o coada Q in care introduc pe rand nodurile care
	
// au gradul exterior zero
	
// complexitate O(N+M)
	
 
	
void solve(void)
	
{
	
    int i, x; vector<int>::iterator it;
	
    
	
    for(x = 1; x <= N; x++)
	
     if(deg[x] == 0) Q[++Q[0]] = x;
	
 
	
    for(i = 1; i <= N; i++)
	
    {
	
        x = Q[i];
	
        for(it = G[x].begin(); it != G[x].end(); ++it)
	
        {
	
            deg[*it]--;
	
            if(deg[*it] == 0) Q[++Q[0]] = *it;
	
        }
	
    }
	
}
	
 
	
void read_data(void)
	
{
	
    int i, a, b;
	
 
	
    scanf("%d %d\n", &N, &M);
	
    for(i = 1; i <= M; i++)
	
        scanf("%d %d\n", &a, &b), G[a].pb(b), deg[b]++;
	
}
	
 
	
void write_data(void)
	
{
	
    int i;
	
 
	
    for(i = 1; i <= N; i++)
	
        printf("%d ", Q[i]);
	
}
	
 
	
int main(void)
	
{
	
    freopen("sortaret.in", "rt", stdin);
	
    freopen("sortaret.out", "wt", stdout);
	
 
	
    read_data();
	
    solve();
	
    write_data();
	
 
	
    return 0;
	
}

// #include <bits/stdc++.h>

// using namespace std;

// ifstream f("sortaret.in");
// ofstream g("sortaret.out");

// vector<int> v[50001];
// int n, m, ge[50001];

// void citire()
// {
//     f >> n >> m;
//     for (int i = 1; i <= m; i++)
//     {
//         int x, y;
//         f >> x >> y;
//         v[x].push_back(y);
//         ge[y]++;
//     }
// }

// vector <int> q;
// int viz[50001];

// void rez()
// {
//     q.push_back(0);
//     for (int i = 1; i <= n; i++)
//         if (!ge[i]) 
//         {
//             q.push_back(i);
//             q[0]++;
//             viz[i] = 1;
//         }
//     for (int i = 1; i <= q[0]; i++) {
//         cout<<i<<": ";
//         int x=q[i];
//         for(auto& j:v[x])
//         {
//             cout<<j<<" ";
//             ge[j]--;
//             if(ge[j]==0)
//             {
//                 q.push_back(j);
//                 q[0]++;
//             }
//         }
//         cout<<'\n';
//     }
// }

// void afis()
// {
//     for(int i=1; i<=q[0]; i++) g<<q[i]<<" ";
// }

// int main()
// {
//     citire();
//     rez();
//     afis();
// }