Pagini recente » Cod sursa (job #1157496) | Cod sursa (job #515459) | Cod sursa (job #2345016) | Cod sursa (job #3233837) | Cod sursa (job #2509490)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<int> graf[100005], grafInvers[100005];
bool viz1[100005], viz2[100005];
stack<int> S;
vector<int> currSol;
vector<vector<int> > sol;
void read()
{
int x, y;
f>>n>>m;
for(int i = 0; i<m; ++i)
{
f>>x>>y;
graf[x].push_back(y);
grafInvers[y].push_back(x);
}
}
void dfs(int node)
{
viz1[node] = true;
for(int nd : graf[node])
{
if(!viz1[nd])
{
dfs(nd);
}
}
S.push(node);
}
void dfsInvers(int node)
{
viz2[node] = true;
for(int nd : grafInvers[node])
{
if(!viz2[nd])
{
dfsInvers(nd);
}
}
currSol.push_back(node);
}
void solve()
{
for(int i = 1; i<=n; ++i)
{
if(!viz1[i])
dfs(i);
}
while(!S.empty())
{
int i = S.top();
S.pop();
if(!viz2[i])
{
dfsInvers(i);
sol.push_back(currSol);
currSol.clear();
}
}
}
void print()
{
for(auto p : sol)
{
for(int nod : p)
{
g<<nod<<" ";
}
g<<"\n";
}
}
int main()
{
read();
solve();
print();
return 0;
}