#include <bits/stdc++.h>
struct repRang{
int rep;
int rang;
};
class Edge{
public:
int i, j, cost;
Edge(int _i, int _j, int _cost) : i(_i), j(_j), cost(_cost){}
friend bool operator<(const Edge& e1, const Edge& e2)
{
return e1.cost < e2.cost;
}
};
const int nmax = 100005;
using namespace std;
int extractMin(priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& pq){
int temp = pq.top().second;
pq.pop();
return temp;
}
class Graph{
int V, E;
vector<pair<int, int>> adj[nmax];
bool directed, weighted;
static int findRep(repRang*, int);
static void reunion(repRang*, int, int);
public:
static void disjoint();
Graph(bool, bool);
void build(ifstream&);
void Kruskal(ofstream&);
void BellmanFord(ofstream&);
void Dijkstra(ofstream&);
void DF(int, bool*);
void DFsol(ofstream&);
void BFS(ofstream&, ifstream&);
void DFts(int, bool*, stack<int>&);
void TopologicalSort(ofstream&);
};
void Graph::DFts(int src, bool* vis, stack<int>& st){
for(auto ngb: adj[src])
if(vis[ngb.first] == false)
{ vis[src] = true;
DFts(ngb.first, vis, st);
}
st.push(src);
}
void Graph::TopologicalSort(ofstream& fout){
bool vis[nmax] = {false};
stack<int> st;
for(int i = 1; i <= V; ++i)
if(!(vis[i]))
DFts(i, vis, st);
while(st.size())
{
fout << st.top() << ' ';
st.pop();
}
}
Graph::Graph(bool _directed, bool _weighted) : directed(_directed), weighted(_weighted){}
int Graph::findRep(repRang* info, int x){
if(x == info[x].rep)
return x;
return (info[x].rep = findRep(info, info[x].rep));
}
void Graph::reunion(repRang* info, int x, int y){
int repX = findRep(info, x);
int repY = findRep(info, y);
if(info[repX].rang > info[repY].rang)
info[repX].rep = repY;
else
if(info[repX].rang < info[repY].rang)
info[repY].rep = repX;
else
{
info[repX].rang++;
info[repY].rep = repX;
}
}
void Graph::disjoint(){
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
repRang* info = new repRang[nmax];
int N, M;
fin >> N >> M;
for(int i = 1; i <= N; ++i)
info[i].rep = i;
for(int i = 1; i <= M; ++i){
int cod, x, y;
fin >> cod >> x >> y;
if(cod == 2)
if(findRep(info, x) == findRep(info, y))
fout << "DA\n";
else
fout << "NU\n";
else
reunion(info, x, y);
}
}
void Graph::build(ifstream& fin){
fin >> V >> E;
for(int i = 1; i <= E; ++i){
int src, dest, cost;
fin >> src >> dest;
adj[src].push_back(make_pair(dest, 0));
if(weighted){
fin >> cost;
adj[src][adj[src].size() - 1].second = cost;
}
if(!directed)
adj[dest].push_back(make_pair(src, cost));
}
}
void Graph::Kruskal(ofstream& fout){
vector<pair<int, int>> sol;
repRang reps[nmax];
vector<Edge> edges;
for(int i = 1; i <= V; ++i)
{
int src = i;
for(int j = 0; j < adj[i].size(); ++j){
int dest = adj[i][j].first;
int cost = adj[i][j].second;
if(src > dest){
Edge temp_edge = Edge(src, dest, cost);
edges.push_back(temp_edge);
}
}
}
int total = 0;
sort(edges.begin(), edges.end());
for(int i = 1; i <= V; ++i)
{
reps[i].rep = i;
reps[i].rang = 0;
}
int cnt = 0;
int i = 0;
for(;i < edges.size() && cnt <= E - 1; ++i){
Edge temp_edge = edges[i];
if(findRep(reps, edges[i].i) != findRep(reps, edges[i].j))
{
++cnt;
sol.push_back(make_pair(temp_edge.i, temp_edge.j));
reunion(reps, temp_edge.i, temp_edge.j);
total += temp_edge.cost;
}
}
fout << total << '\n';
fout << cnt << '\n';
for(auto edg: sol){
fout << edg.first << ' ' << edg.second << '\n';
}
}
void Graph::BellmanFord(ofstream& fout){
queue<int> q;
bool inQ[nmax] = {false};
int distMin[nmax];
int cnt[nmax] = {0};
distMin[1] = 0;
for(int i = 2; i <= V; ++i)
distMin[i] = INT_MAX / 2;
q.push(1);
inQ[1] = true;
while(!(q.empty())){
int i = q.front();
q.pop();
inQ[i] = false;
for(auto ngb: adj[i]){
int j = ngb.first;
int cost = ngb.second;
if(distMin[i] + cost < distMin[j]){
distMin[j] = distMin[i] + cost;
if(inQ[j] == false)
{ q.push(j);
inQ[j] = true;
++cnt[j];
if(cnt[j] > V)
{
fout << "Ciclu negativ!\n";
return;
}
}
}
}
}
for(int i = 2; i <= V; ++i)
fout << distMin[i] << ' ';
}
void Graph::Dijkstra(ofstream& fout){
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; /// tine perechi de tip (cost, nod)
int dMin[nmax];
dMin[1] = 0;
for(int i = 2; i <= V; ++i)
dMin[i] = INT_MAX / 2;
pq.push(make_pair(0, 1));
bool inQ[nmax] = {false};
while(!(pq.empty())){
int crt = extractMin(pq);
if(inQ[crt] == true)
continue;
inQ[crt] = true;
for(auto ngb: adj[crt]){
int vv = ngb.first;
int ccost = ngb.second;
if(ccost + dMin[crt] < dMin[vv])
{
dMin[vv] = ccost + dMin[crt];
pq.push(make_pair(dMin[vv], vv));
}
}
}
for(int i = 2; i <= V; ++i)
if(dMin[i] != INT_MAX / 2)
fout << dMin[i] << ' ';
else fout << 0 << ' ';
}
void Graph::DF(int src, bool* vis){
for(auto ngb: adj[src]){
if(vis[ngb.first] == false)
{
vis[ngb.first] = true;
DF(ngb.first, vis);
}
}
}
void Graph::DFsol(ofstream& fout){
int total = 0;
bool vis[nmax] = {false};
for(int i = 1; i <= V; ++i)
if(vis[i] == false)
{
total++;
DF(i, vis);
}
fout << total;
}
void Graph::BFS(ofstream& fout, ifstream& fin){
int src;
fin >> V >> E;
fin >> src;
for(int i = 1; i <= E; ++i)
{
int k, j;
fin >> k >> j;
adj[k].push_back(make_pair(j, 0));
}
queue<int> q;
int dist[nmax];
for(int i = 1; i <= V; ++i)
dist[i] = - 1;
q.push(src);
dist[src] = 0;
while(!(q.empty())){
int top = q.front();
q.pop();
for(auto ngb : adj[top])
if(dist[ngb.first] == - 1){
dist[ngb.first] = dist[top] + 1;
q.push(ngb.first);
}
}
for(int i = 1; i <= V; ++i)
fout << dist[i] << ' ';
}
int main()
{
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
Graph g(true, false);
g.build(fin);
g.TopologicalSort(fout);
return 0;
}