Pagini recente » Cod sursa (job #647965) | Cod sursa (job #1053213) | Cod sursa (job #622277) | Cod sursa (job #2570638) | Cod sursa (job #1938561)
#include <cstdio>
#include <vector>
using namespace std;
vector <int> v[100005],w[100005],sol[100005];
bool vizv[100005],vizw[100005];
int k,n,m,i,x,y,l,nrcomp,componente,st[100005];
void dfsv(int x)
{
vizv[x]=1;
int i,l=v[x].size();
for (i=0; i<l; i++)
if (vizv[v[x][i]]==0)
dfsv(v[x][i]);
st[++k]=x;
}
void dfsw(int x)
{
vizw[x]=1;
sol[componente].push_back(x);
int i,l=w[x].size();
for (i=0; i<l; i++)
if (vizw[w[x][i]]==0)
dfsw(w[x][i]);
}
int main()
{
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);
v[x].push_back(y);
w[y].push_back(x);
}
for (i=1; i<=n; i++)
if (vizv[i]==0)
dfsv(i);
while (k!=0)
{
x=st[k]; k--;
if (vizw[x]==0)
{
componente++;
dfsw(x);
}
}
printf("%d\n",componente);
for (nrcomp=1; nrcomp<=componente; nrcomp++)
{
l=sol[nrcomp].size();
for (i=0; i<l; i++)
printf("%d ",sol[nrcomp][i]);
printf("\n");
}
return 0;
}