Pagini recente » Diferente pentru utilizator/ericmaslim intre reviziile 2 si 1 | Profil lsmloegndaa | Cod sursa (job #1750624) | Diferente pentru problema/pescari intre reviziile 4 si 3 | Cod sursa (job #1750623)
#include <cstdio>
#include<vector>
#define MAXN 100000
#define MAXM 200000
using namespace std;
vector<int>v[MAXN+1];
int ans, n, m, lista[MAXN+1], next[MAXM+1], val[MAXM+1], id[MAXN+1], st[MAXN+1], low[MAXN+1], index, p, k;
bool ok[MAXN+1];
inline int minim(int a, int b)
{
return (a < b ? a : b);
}
inline void adauga(int x, int y)
{
val[++p]=y;
next[p]=lista[x];
lista[x]=p;
}
void tarjan(int nod)
{
int p, vecin;
index++;
id[nod]=low[nod]=index;
st[++k]=nod;
ok[nod]=1;
p=lista[nod];
while(p)
{
vecin=val[p];
if(!id[vecin])
{
tarjan(vecin);
low[nod]=minim(low[nod], low[vecin]);
}
else if(ok[vecin])
low[nod]=minim(low[nod], low[vecin]);
p=next[p];
}
if(low[nod]==id[nod])
{
ans++;
while(st[k] != nod)
{
ok[st[k]]=0;
v[ans].push_back(st[k]);
--k;
}
v[ans].push_back(st[k]);
ok[st[k]]=0;
--k;
}
}
void afisare()
{
int i, j;
printf("%d\n", ans);
for(i=1;i<=ans;++i)
{
for(j=0;j<v[i].size();++j)
printf("%d ", v[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int i, x, y;
scanf("%d%d", &n, &m);
for(i=1;i<=m;++i)
scanf("%d%d", &x, &y), adauga(x, y);
for(i=1;i<=n;++i)
if(!id[i])
tarjan(i);
afisare();
return 0;
}