#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
class Graph {
int nrNodes; //number of nodes
vector<vector< pair<int, double>> > edges; // list of connections between nodes
public:
Graph(int _nrNodes);
int getNrNodes() const;
void setEdge(int node, int neighbour, double cost);
vector<pair<int, double>>getNeighbours(int node);
int nrConnectedComponents();
void printEdges();
vector<int> minDistanceBFS(int start);
~Graph();
private:
void DFS(int node, vector<int>& visited);
};
//---------------------------------------------
Graph::Graph(int _nrNodes)
{
this -> nrNodes = _nrNodes;
this -> edges.resize(this -> nrNodes + 1, vector<pair<int, double>>());
/*
* Nodes start at 1, but index starts at 0
*/
}
int Graph::getNrNodes() const
{
return this -> nrNodes;
}
int Graph::nrConnectedComponents()
{
int ans = 0;
vector<int>visited(this -> nrNodes+1, 0);
for(int i = 1 ; i <= this -> nrNodes; ++i)
if(visited[i] == 0)
{
DFS(i, visited);
++ans;
}
return ans;
}
void Graph::DFS(int start, vector<int>& visited)
{
visited[start] = 1;
for(int i = 0; i < edges[start].size(); ++i)
{
int neighbour = edges[start][i].first; // get neighbour without cost
if(visited[neighbour] == 0)
{
visited[neighbour] = 1;
DFS(neighbour, visited);
}
}
}
Graph::~Graph()
{
this -> nrNodes = 0;
for(int i = 1; i <= edges.size(); ++i)
this -> edges[i].clear();
}
void Graph::printEdges()
{
for(int i = 1; i < edges.size(); i++)
{
cout << i<< ": ";
for(auto it: edges[i])
cout << it.first<< " ";
cout << "\n";
}
}
void Graph::setEdge(int node, int neighbour, double cost)
{
this ->edges[node].push_back({neighbour, cost});
}
vector<int> Graph::minDistanceBFS(int start)
{
vector<int>distances(this->nrNodes + 1, -1);
distances[start] = 0;
queue<int>toBeVisited;
toBeVisited.push(start);
while(!toBeVisited.empty())
{
int x = toBeVisited.front();
toBeVisited.pop();
for(auto it: this->edges[x])
if(distances[it.first] == -1)
{
distances[it.first] = distances[x] + 1;
toBeVisited.push(it.first);
}
} //while loop ended
return distances;
}
vector<pair<int, double>> Graph::getNeighbours(int node)
{
return this -> edges[node];
}
//-------------------------------------------------------------------
class DirectedGraph: public Graph {
void TarjanDFS(int start, int& counterID,
stack<int>&nodeStack, vector<bool>&onStack,
vector<vector<int>>&scc,
vector<int>&nodeID, vector<int>&lowestLink);
void TopologicalDFS(int node, stack<int>&sorted,
vector<bool>&visited);
public:
DirectedGraph(int _nrNodes);
void addEdge(int node, int neighbour, double cost);
vector<vector<int>> getStronglyConnected();
stack<int> TopologicalSorting();
~DirectedGraph();
};
//----------------------------------------------------------------------
DirectedGraph::DirectedGraph(int _nrNodes): Graph(_nrNodes) {}
void DirectedGraph::addEdge(int node, int neighbour, double cost)
{
this -> setEdge(node, neighbour, cost);
}
vector<vector<int>> DirectedGraph::getStronglyConnected()
{ // initializing everything we need for the Tarjan algorithm
vector<vector<int>> scc;
stack<int> nodeStack;
vector<bool> onStack(this -> getNrNodes()+1, false);
vector<int> lowestLink(this -> getNrNodes()+1, -1);
vector<int> nodeID(this -> getNrNodes()+1, -1);
int counterID = 0;
for(int node = 1; node <= this -> getNrNodes(); ++node)
if(nodeID[node] == -1)
TarjanDFS(node, counterID, nodeStack,
onStack, scc, nodeID, lowestLink);
/*
* scc = strongly connected component
* TarjanDFS() modifies vector<vector<int>> scc
* so vector<vector<int>> scc will contain all the needed components
*/
return scc;
}
void DirectedGraph::TarjanDFS(int node, int& counterID,
stack<int>&nodeStack,
vector<bool>& onStack,
vector<vector<int>>&scc,
vector<int> &nodeID,
vector<int>&lowestLink)
{
vector<int> component;
nodeID[node] = counterID;
lowestLink[node] = counterID++;
nodeStack.push(node);
onStack[node] = true;
for(auto it: this->getNeighbours(node))
{
int neighbour = it.first; // node -> first; cost -> second
if(nodeID[neighbour] == -1) // if neighbour not visited
TarjanDFS(neighbour, counterID, nodeStack,
onStack, scc, nodeID,
lowestLink);
if(onStack[neighbour]) //if neighbour is on stack
lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);
}
if(lowestLink[node] == nodeID[node]) // if this is true then node is the beginning of a scc
{
while(!nodeStack.empty())
{
int nodeToPop = nodeStack.top();
component.push_back(nodeToPop);
onStack[nodeToPop] = false;
nodeStack.pop();
if(nodeToPop == node)
break;
}
scc.push_back(component);
component.clear();
}
}
DirectedGraph::~DirectedGraph() {}
stack<int> DirectedGraph::TopologicalSorting()
{
stack<int> sorted;
vector<bool> visited(this->getNrNodes() + 1, false);
for(int node = 1; node < visited.size(); ++node)
if(!visited[node])
TopologicalDFS(node, sorted, visited);
/*
* -> TopologicalDFS() modifies the sorted vector
* -> the sorted nodes are the nodes' times in descending order
*/
return sorted;
}
void DirectedGraph::TopologicalDFS(int node, stack<int>&sorted,
vector<bool>&visited)
{
visited[node] = true;
for(auto it: this->getNeighbours(node))
{
int neighbour = it.first;
if (!visited[neighbour])
TopologicalDFS(neighbour, sorted, visited);
}
sorted.push(node);
}
int main()
{ ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y,s;
cin >> n >> m;
DirectedGraph *ug = new DirectedGraph(n);
for(int i = 1; i <= m; i++)
{
cin >> x >> y;
ug -> addEdge(x, y, 0);
}
stack<int> sorted = ug -> TopologicalSorting();
while(!sorted.empty())
{
cout << sorted.top()<< " ";
sorted.pop();
}
return 0;
}