Pagini recente » Cod sursa (job #1869019) | Cod sursa (job #798774) | Cod sursa (job #1045531) | Cod sursa (job #2579718) | Cod sursa (job #2272617)
#include <cstdio>
#include <vector>
#include <iostream>
#define DIMN 100001
using namespace std;
int g,sol,elem,niv[DIMN],low[DIMN],s[DIMN],f[DIMN];
vector <int> v[DIMN],sl[DIMN];
void dfs (int nod){
int vecin,i;
g++;
niv[nod]=g;
low[nod]=g;
s[++elem]=nod;
f[nod]=1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (!niv[vecin]){
dfs(vecin);
low[nod]=min(low[nod],low[vecin]);
}
else if (f[vecin])
low[nod]=min(low[nod],low[vecin]);
}
if (low[nod]==niv[nod]){
sol++;
do{
sl[sol].push_back(s[elem]);
f[s[elem]]=0;
elem--;
} while (s[elem+1]!=nod);
}
}
int main()
{
FILE *fin=fopen ("ctc.in","r");
FILE *fout=fopen ("ctc.out","w");
int n,m,x,y,i,j;
fscanf (fin,"%d%d",&n,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
}
for (i=1;i<=n;i++){
if (!niv[i])
dfs (i);
}
fprintf (fout,"%d\n",sol);
for (i=1;i<=sol;i++){
for (j=0;j<sl[i].size();j++)
fprintf (fout,"%d ",sl[i][j]);
fprintf (fout,"\n");
}
return 0;
}