Pagini recente » Cod sursa (job #2785788) | Cod sursa (job #1071783) | Cod sursa (job #1889959) | Cod sursa (job #1689886) | Cod sursa (job #1412900)
#include <fstream>
#include <vector>
#include <stack>
#define maxn 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> v[maxn];
vector <int> g[maxn];
stack <int> st;
int n, m, x, y, depth[maxn], lowlink[maxn], nrctc=0;
bool viz[maxn], in_stack[maxn];
void dfs(int x, int lvl)
{
viz[x]=1;
st.push(x);
in_stack[x]=1;
depth[x]=lvl;
lowlink[x]=lvl;
for(int i=0; i<g[x].size(); i++)
{
int y=g[x][i];
if(!viz[y])
{
dfs(y, lvl+1);
lowlink[x]=min(lowlink[x], lowlink[y]);
}
else if(in_stack[y])
lowlink[x]=min(lowlink[x], lowlink[y]);
}
int k=0;
if(depth[x]==lowlink[x])
{
nrctc++;
while(st.top()!=x)
{
v[nrctc].push_back(st.top());
in_stack[st.top()]=0;
st.pop();
}
v[nrctc].push_back(x);
st.pop();
in_stack[x]=0;
}
}
int main()
{
fin >> n >> m;
for(int i=1; i<=m; i++)
{
fin >> x >> y;
g[x].push_back(y);
}
for(int i=1; i<=n; i++)
if(!viz[i])
dfs(i, 0);
fout << nrctc << '\n';
for(int i=1; i<=nrctc; i++)
{
for(int j=0; j<v[i].size(); j++)
fout << v[i][j] << ' ';
fout << '\n';
}
return 0;
}