Pagini recente » Cod sursa (job #218225) | Cod sursa (job #906884) | Cod sursa (job #1734657) | Cod sursa (job #5665) | Cod sursa (job #932980)
Cod sursa(job #932980)
#include<cstdio>
#include<stack>
#include<vector>
#define NMax 100005
using namespace std;
int idx[NMax],lowlink[NMax];
int in_st[NMax],crt,nr_ctc;
vector<int> vc[NMax],ctc[NMax];
stack<int> S;
void df (int nod)
{
crt++;
idx[nod]=crt;
lowlink[nod]=crt;
S.push(nod), in_st[nod]=1;
int i,lg=vc[nod].size();
for (i=0; i<lg; i++)
if (!idx[vc[nod][i]])
{
df(vc[nod][i]);
lowlink[nod]=min(lowlink[nod],lowlink[vc[nod][i]]);
}
else if (in_st[vc[nod][i]])
lowlink[nod]=min(lowlink[nod],idx[vc[nod][i]]);
if (idx[nod]==lowlink[nod])
{
nr_ctc++;
int aux;
do
{
aux=S.top(), S.pop();
in_st[aux]=0;
ctc[nr_ctc].push_back(aux);
} while (aux!=nod);
}
}
int main ()
{
int n,m,i,lg,x,y,j;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
vc[x].push_back(y);
}
for (i=1; i<=n; i++)
if (!idx[i])
df(i);
printf("%d\n",nr_ctc);
for (i=1; i<=nr_ctc; i++, printf("\n"))
{
lg=ctc[i].size();
for (j=0; j<lg; j++)
printf("%d ",ctc[i][j]);
}
return 0;
}