Pagini recente » Cod sursa (job #2545616) | Cod sursa (job #2777735) | Cod sursa (job #3004350) | Cod sursa (job #425231) | Cod sursa (job #2665062)
#include <iostream>
#include <list>
#include <stack>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int nr = 0;
int dis = 0; /// the number of discovery
void dfs(int start, list<int> ad[],int d[], int onstack[], list <int> rez[], int low[], stack <int> &st)
{
///housekeeping stuff :)
d[start] = low[start] = ++ dis;
onstack[start] = 1;
st.push(start);
for(auto &child : ad[start])
{
if(d[child] == 0)
{
dfs(child,ad,d,onstack,rez,low,st);
}
///on callback
if(onstack[child] == 1)
low[start] = min(low[start],low[child]);
}
///after we visited all neighbours
if(d[start] == low[start])
{
///hopa! it seems that the current node starts a SCC!
nr ++;
while(st.top() != start)
{
rez[nr].push_front(st.top());
st.pop();
onstack[start] = 0;
}
rez[nr].push_front(st.top());
st.pop();
}
}
int main()
{
int n,m,start;
fin>>n>>m;
list <int> ad[n+1];
for(int i = 0; i < m; i ++)
{
int x,y;
fin >> x >> y;
ad[x].push_back(y);
}
int d[n+1] = {0};
int onstack[n+1] = {0};
int low[ n + 1] = {0};
stack <int> st;
list <int> rez[ n + 1];
for(int i=1; i<=n; i++)
if(d[i] == 0)
{
start = i;
dfs(start,ad,d,onstack,rez,low,st);
}
fout << nr<<"\n";
for(int i = 1; i <= nr ; i ++)
{
for(auto &it: rez[i])
fout<<it<<" ";
fout<<"\n";
}
return 0;
}