Pagini recente » Cod sursa (job #2858799) | Cod sursa (job #1928263) | Cod sursa (job #2470358) | Cod sursa (job #1889482) | Cod sursa (job #311923)
Cod sursa(job #311923)
#include<stdio.h>
#include<vector>
#define N 100007
#define M 200007
using namespace std;
int n,m,*a[N],*b[N],x[M],y[M],da[N],db[N],nrc=0,nr;
vector<int> c[N];
vector<int> v;
bool viz1[N],viz2[N];
void citire()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
++da[x[i]];
++db[y[i]];
}
for(int i=1;i<=n;i++)
{
a[i]=new int[da[i]+1];
b[i]=new int[db[i]+1];
a[i][0]=b[i][0]=0;
}
for(int i=1;i<=m;i++)
{
a[x[i]][++a[x[i]][0]]=y[i];
b[y[i]][++b[y[i]][0]]=x[i];
}
}
/*
void afisare(int **a)
{
for(int i=1;i<=n;i++)
{
printf("%d : %d varfuri : ",i,a[i][0]);
for(int j=1;j<=a[i][0];j++)
printf("%5d",a[i][j]);
printf("\n");
}
printf("\n");
}
*/
void df1(int x)
{
viz1[x]=true;
v.push_back(x);
for(int i=1;i<=a[x][0];++i)
if(!viz1[a[x][i]])
df1(a[x][i]);
}
void df2(int x)
{
viz2[x]=true;
c[nrc].push_back(x);
for(int i=1;i<=b[x][0];++i)
if(viz1[b[x][i]] && !viz2[b[x][i]])
df2(b[x][i]);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
//afisare(a);
//afisare(b);
for(int i=1;i<=n;++i)
if(!viz2[i])
{
df1(i);//marcheaza varfurile in care se poate ajunge din i si le adauga in v
//parcurg v si determin comp tare conexe ale varfurilor sale
nr=v.size();
for(int j=1;j<nr;++j)
if(!viz2[v[j]])
{
++nrc;
df2(v[j]);
}
}
printf("%d\n",nrc);
for(int i=1;i<=nrc;++i)
{
for(int j=0;j<c[i].size();++j)
printf("%d ",c[i][j]);
printf("\n");
}
return 0;
}