Pagini recente » Cod sursa (job #1596606) | Cod sursa (job #2735115) | Cod sursa (job #127215) | Cod sursa (job #756791) | Cod sursa (job #3201476)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <chrono>
#include <numeric>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <stack>
#include <queue>
#include <list>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
#define M 1000000007
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<class T> T nxt() {
T x;
cin >> x;
return x;
}
// // Gets the topological order of a graph using sets
// // If its not possible,check size()<n
// vi getTopologicalOrder(const vector<set<int>>& v){
// int n=v.size()-1;
// vi inDegree(n+1);
// for(int i=1;i<=n;++i){
// for(auto y:v[i]){
// ++inDegree[y];
// }
// }
// vb used(n+1);
// vi order;
// queue<int> q;
// for(int i=1;i<=n;++i){
// if(!inDegree[i]){
// q.push(i);
// order.push_back(i);
// used[i]=1;
// }
// }
// while(q.size()){
// int x=q.front();
// q.pop();
// for(auto y:v[x]){
// --inDegree[y];
// if(!inDegree[y]&&!used[y]){
// q.push(y);
// used[y]=1;
// order.push_back(y);
// }
// }
// }
// return order;
// }
// Gets the topological order of a graph using vector of vectors for graph
// If its not possible,check size()<n
vi getTopologicalOrder(const vvi& v){
int n=v.size()-1;
vi inDegree(n+1);
for(int i=1;i<=n;++i){
for(auto y:v[i]){
++inDegree[y];
}
}
vb used(n+1);
vi order;
queue<int> q;
for(int i=1;i<=n;++i){
if(!inDegree[i]){
q.push(i);
order.push_back(i);
used[i]=1;
}
}
while(q.size()){
int x=q.front();
q.pop();
for(auto y:v[x]){
--inDegree[y];
if(!inDegree[y]&&!used[y]){
q.push(y);
used[y]=1;
order.push_back(y);
}
}
}
return order;
}
void Solve(){
int n,m;
fin>>n>>m;
// vector<set<int>> v(n+1);
vvi v(n+1);
for(int i=0;i<m;++i){
int x,y;
fin>>x>>y;
// v[x].insert(y);
v[x].push_back(y);
}
vi order=getTopologicalOrder(v);
for(auto x:order){
fout<<x<<' ';
}
}
int main(){
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// std::string file="FILE";
// std::ifstream in(file+".in");
// std::streambuf *finbuf = std::fin.rdbuf(); //save old buf
// fin.rdbuf(in.rdbuf()); //redirect std::fin
// std::ofstream out(file+".out");
// std::streambuf *foutbuf = std::fout.rdbuf(); //save old buf
// fout.rdbuf(out.rdbuf()); //redirect std::fout
Solve();
// std::fin.rdbuf(finbuf); //reset to standard input again
// std::fout.rdbuf(foutbuf); //reset to standard output again
return 0;
}