Pagini recente » Cod sursa (job #171107) | Cod sursa (job #2153442) | Cod sursa (job #1135235) | Cod sursa (job #332913) | Cod sursa (job #2289957)
#include <bits/stdc++.h>
using namespace std;
int niv[100010];
int low[100010];
int inst[100010];
vector<int> g[100010];
vector<int> r[100010];
int st[100010];
int lst, lr;
int ind;
void dfs(int nod)
{
st[lst++] = nod;
niv[nod] = ++ind;
low[nod] = niv[nod];
inst[nod] = 1;
for(auto next : g[nod])
{
if(niv[next] == 0)
{
dfs(next);
low[nod] = min(low[nod], low[next]);
}
else if(inst[nod])
low[nod] = min(low[nod], low[next]);
}
if(niv[nod] == low[nod])
{
st[lst] = -1;
while(st[lst] != nod)
{
r[lr].push_back(st[lst - 1]);
inst[st[lst - 1]] = 0;
lst--;
}
lr++;
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
g[a].push_back(b);
}
for(int i = 1; i <= n; i++)
{
if(niv[i] == 0)
{
dfs(i);
}
}
printf("%d\n", lr);
for(int i = 0; i < lr; i++)
{
for(int j = 0; j < r[i].size(); j++)
printf("%d ", r[i][j]);
printf("\n");
}
return 0;
}