Pagini recente » Cod sursa (job #950995) | Cod sursa (job #1393763) | Statistici ishootniggers4fun69420 (ishootniggers4fun69420) | Cod sursa (job #1163491) | Cod sursa (job #2439761)
#include <iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
struct nod
{
vector<int> ext;
vector<int> in;
};
vector<nod> G;
long long N, M;
void read()
{
//cout<<"Reading..."<<endl;
fin>>N>>M;
//cout<<"Reading dimensions"<<endl;
G.resize(N+5);
for(long long i = 1; i<=M; i++)
{
int x,y;
fin>>x>>y;
G[x].ext.push_back(y);
G[y].in.push_back(x);
}
//cout<<"Finished reading"<<endl<<endl;
}
void Kahn()
{
queue<int> S;
vector<int> L;
for(unsigned long i = 1; i<=N; i++)
{
if(G.at(i).in.empty()) S.push(i);
}
//cout<<S.size()<<" corners"<<endl;
while(!S.empty())
{
int n = S.front();
S.pop();
L.push_back(n);
// cout<<"n="<<n<<endl;
// cout<<"L={";
// for(unsigned int k = 0;k<L.size();k++) cout<<L[k]<<" ";
// cout<<"}"<<endl;
if(!G[n].ext.empty())
{
for(unsigned int v = 0; v<G[n].ext.size(); v++)
{
// if(n==9)
// {
// cout<<"Entered last loop ext = "<<G[n].ext.size()<<" in = "<<G[n].in.size()<<endl;
// }
int c = G.at(n).ext.at(v);
//cout<<"Deleting the edge of "<<n<<" to "<<c<<endl;
//cout<<"Before:";
//for(unsigned int k = 0; k<G[c].in.size(); k++) cout<<G[c].in[k]<<" ";
//cout<<endl;
G[c].in.erase(remove(G[c].in.begin(),G[c].in.end(),n),G[c].in.end());
//cout<<"After:";
//for(unsigned int k = 0; k<G[c].in.size(); k++) cout<<G[c].in[k]<<" ";
//cout<<endl;
if(G[c].in.empty())
{
//cout<<"Pushing "<<c<<" into S"<<endl;
S.push(c);
}
}
}
}
for(unsigned int i = 0; i<L.size(); i++)
fout<<L.at(i)<<" ";
//cout<<endl;
}
int main()
{
read();
Kahn();
}