Pagini recente » Cod sursa (job #1266789) | Cod sursa (job #748917) | Cod sursa (job #564561) | Cod sursa (job #150602) | Cod sursa (job #2921261)
#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();
// }