Cod sursa(job #2576787)

Utilizator ApetriiRaduApetrii Radu ApetriiRadu Data 6 martie 2020 22:52:33
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define sz(x) x.size()
class Parser{
private:
    static const int SIZE=1e5;
    char str[SIZE];

    int ptr;
    FILE *fin;
    char getChar(){
    if(ptr==SIZE)
        {fread(str,sizeof(char),SIZE,fin);
         ptr=0;
        }
        return str[ptr++];
    }
    int getInt(){
     char chr=getChar();
     while(!isdigit(chr) && chr!='-')
         chr=getChar();
     int sgn=+1;
     if(chr=='-')
        sgn=-1,chr=getChar();

    int nr=0;
    while(isdigit(chr))
    {
        nr=nr*10+chr-'0';
        chr=getChar();
    }
    return nr*sgn;
    }
public:
    Parser(const char* str):
        ptr(SIZE),fin(fopen(str,"r")){}
    ~Parser(){fclose(fin);}
friend Parser& operator>>(Parser& in,int& nr)
{nr=in.getInt();
 return in;
}
};
Parser fin("sortaret.in");
ofstream fout("sortaret.out");
const int NMAX=5e4+5;
vector<int>G[NMAX];
bool uz[NMAX];
vector<int>ans;
int n,m;
void dfs(int x)
{uz[x]=1;
 FOR(i,0,G[x].size())
    if(!uz[G[x][i]])
     dfs(G[x][i]);
 ans.pb(x);
}
void solve() {
fin>>n>>m;
FOR(i,1,m+1)
   {int x,y;
    fin>>x>>y;
    G[x].pb(y);
   }
FOR(i,1,n+1)
   if(!uz[i])
      dfs(i);
reverse(ans.begin(),ans.end());
FOR(i,0,sz(ans))
   fout<<ans[i]<<' ';
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t=1;
    //cin>>t;
  	while(t--)
         solve();
    return 0;

}