Pagini recente » Cod sursa (job #1729423) | Cod sursa (job #1753319) | Cod sursa (job #51506) | Cod sursa (job #236619) | Cod sursa (job #649455)
Cod sursa(job #649455)
#include<fstream>
#include<vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int N, M;
vector<int>graph[50001];
int grad[50001];
class heap
{ int h[65536];
int pos[50001];
bool in_h[50001];
int dim;
public:
heap()
{ dim = 0;
}
void push(int node)
{ if(in_h[node])
return;
in_h[node] = 1;
h[++dim] = node;
pos[node] = dim;
up_heap(dim);
}
void pop()
{ in_h[h[1]] = 0;
pos[h[1]] = -1;
pos[h[dim]] = 1;
swap(h[1], h[dim]);
dim--;
down_heap(1);
}
void up_heap(int p)
{ while(p > 1 && grad[h[p]] < grad[h[p / 2]])
{ swap(h[p], h[p / 2]);
swap(pos[h[p]], pos[h[p / 2]]);
p /= 2;
}
}
void down_heap(int p)
{ int son;
do
{ son = 0;
if(p * 2 <= dim && grad[h[p]] > grad[h[2 * p]]) son = p * 2;
if(p * 2 + 1 <= dim && grad[h[p]] > grad[h[2 * p + 1]] && grad[h[2 * p + 1]] < grad[h[2 * p]]) son = 2 * p + 1;
if(son)
{ swap(h[p], h[son]);
swap(pos[h[p]], pos[h[son]]);
p = son;
}
}while(son);
}
void update(int node)
{ if(pos[node] == -1) return;
up_heap(pos[node]);
down_heap(pos[node]);
}
bool empty()
{ return dim == 0;
}
int root()
{ return h[1];
}
};
heap h;
int main()
{ int i, j, x;
f>>N>>M;
for(i = 1; i <= M; i++)
{ f>>j>>x;
graph[j].push_back(x);
grad[x]++;
}
for(i = 1; i <= N; i++) h.push(i);
while(!h.empty() && grad[h.root()] == 0)
{ i = h.root(); h.pop();
g<<i<<" ";
for(j = 0; j < graph[i].size(); j++)
{ grad[graph[i][j]]--;
h.update(graph[i][j]);
}
}
f.close();
g.close();
return 0;
}