Pagini recente » Cod sursa (job #1654275) | Cod sursa (job #3173059) | Cod sursa (job #349361) | Cod sursa (job #3264394) | Cod sursa (job #3261971)
#include <fstream>
#include <vector>
using namespace std;
class InParser {
vector<char> str;
int ptr;
ifstream fin;
char getChar() {
if (ptr == int(str.size())) {
fin.read(str.data(), str.size());
ptr = 0;
}
return str[ptr++];
}
template<class T>
T getInt() {
char chr = getChar();
while (!isdigit(chr) && chr != '-')
chr = getChar();
int sgn = +1;
if (chr == '-') {
sgn = -1;
chr = getChar();
}
T num = 0;
while (isdigit(chr)) {
num = num * 10 + chr - '0';
chr = getChar();
}
return sgn * num;
}
public:
InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
~InParser() { fin.close(); }
template<class T>
friend InParser& operator>>(InParser& in, T& num) {
num = in.getInt<T>();
return in;
}
};
class OutParser {
vector<char> str;
int ptr;
ofstream fout;
void putChar(char chr) {
if (ptr == int(str.size())) {
fout.write(str.data(), str.size());
ptr = 0;
}
str[ptr++] = chr;
}
template<class T>
void putInt(T num) {
if (num < 0) {
putChar('-');
num *= -1;
}
if (num > 9)
putInt(num / 10);
putChar(num % 10 + '0');
}
public:
OutParser(const char* name) : str(1e5), ptr(0), fout(name) { }
~OutParser() { fout.write(str.data(), ptr); fout.close(); }
template<class T>
friend OutParser& operator<<(OutParser& out, const T num) {
out.putInt(num);
return out;
}
friend OutParser& operator<<(OutParser& out, const char chr) {
out.putChar(chr);
return out;
}
friend OutParser& operator<<(OutParser& out, const char* str) {
for (int i = 0; str[i]; i++)
out.putChar(str[i]);
return out;
}
};
InParser cin("sortaret.in");
OutParser cout("sortaret.out");
using pii = pair<int,int>;
const int nmax = 5e4 + 1 , mmax = 1e5 + 1;
struct q{
int l = 0 , r = -1 , qu[nmax+69];
void push(int &x){qu[++r] = x;}
bool emp(){return l>r;}
int topop(){return qu[l++];}
}ueue;
int start[nmax] , finish[nmax] , n , m , a , b;
pii balls[mmax];
int in[nmax];
signed main()
{
cin >> n >> m;
for(int i = 1 ; i <= m ; ++i){
cin >> a >> b;
in[b]++;
balls[i].first = b;
if(finish[a]) balls[finish[a]].second = i;
finish[a] = i;
if(!start[a]) start[a] = i;
}
for(int i = 1 ; i <= n ; ++i) if(!in[i]) ueue.push(i);
while(!ueue.emp()){
a = ueue.topop() , cout << a << ' ';
for(int i = start[a] ; ; i = balls[i].second){
if(!(--in[balls[i].first])) ueue.push(balls[i].first);
if(balls[i].second == 0) break;
}
}
return 0;
}