Pagini recente » Cod sursa (job #848065) | Cod sursa (job #2309800) | Cod sursa (job #2830422) | Cod sursa (job #225294) | Cod sursa (job #863226)
Cod sursa(job #863226)
// Include
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
// Definitii
#define pb push_back
// Constante
const int sz = (int)1e5+1;
// Functii
void dfs(int node, int start);
void printdfs(int node);
//void backDFS(int node);
// Variabile
ifstream in("ctc.in");
ofstream out("ctc.out");
int nodes, edges;
bool inStack[sz];
bool visited[sz];//, backVisited[sz];
vector<int> graph[sz];
vector<int> reversedGraph[sz];
stack<int> nodesStack;
// Main
int main()
{
in >> nodes >> edges;
int rFrom, rTo; // Teo: <3
for(int i=1 ; i<=edges ; ++i)
{
in >> rFrom >> rTo;
graph[rFrom].pb(rTo);
reversedGraph[rTo].pb(rFrom);
}
while((int)nodesStack.size() != nodes)
{
for(int i=1 ; i<=nodes ; ++i)
{
if(inStack[i])
continue;
dfs(i, i);
}
}
while(!nodesStack.empty())
{
int current = nodesStack.top();
nodesStack.pop();
if(inStack[current])
{
printdfs(current);
out << '\n';
}
}
in.close();
out.close();
return 0;
}
void dfs(int node, int start)
{
visited[node] = true;
vector<int>::iterator it, end = graph[node].end();
for(it=graph[node].begin() ; it!=end ; ++it)
if(!visited[*it])
dfs(*it, start);
if(!inStack[node])
{
nodesStack.push(node);
inStack[node] = true;
}
}
/*void backDFS(int node)
{
backVisited[node] = true;
vector<int>::iterator it, end = graph[node].end();
for(it=graph[node].begin() ; it!=end ; ++it)
if(!backVisited[*it])
backDFS(*it);
}
*/
void printdfs(int node)
{
inStack[node] = false;
out << node << ' ';
vector<int>::iterator it, end = reversedGraph[node].end();
for(it=reversedGraph[node].begin() ; it!=end ; ++it)
{
if(inStack[*it])
printdfs(*it);
}
}