Pagini recente » Cod sursa (job #123115) | Cod sursa (job #2578795) | Cod sursa (job #1202939) | Cod sursa (job #500360) | Cod sursa (job #392503)
Cod sursa(job #392503)
#include<stdio.h>
int deg[100001],*vec[100001];
bool cnx[100001];
int NDFS(int nd)
{
deg[nd]=1;
if(!cnx[nd])
return 1;
else
{
int sum=0;
for(int j=1;j<vec[nd][0];++j)
if(!deg[vec[nd][j]])
{
deg[vec[nd][j]]=1;
sum+=NDFS(vec[nd][j]);
}
return sum+1;
}
}
int main()
{
int aux1,aux2,n,m,i;
int nrc=0;
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=0;i<m;++i)
{
scanf("%d%d",&aux1,&aux2);
if(aux1!=aux2)
{
cnx[aux1]=1;
cnx[aux2]=1;
deg[aux1]++;
deg[aux2]++;
}
}
freopen("dfs.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=0;i<m;++i)
{
scanf("%d%d",&aux1,&aux2);
if(deg[aux1])
{
vec[aux1]=new int[deg[aux1]+1];
vec[aux1][0]=1;
vec[aux1][vec[aux1][0]++]=aux2;
deg[aux1]=0;
}
else
if(aux1!=aux2)
vec[aux1][vec[aux1][0]++]=aux2;
if(deg[aux2])
{
vec[aux2]=new int[deg[aux2]+1];
vec[aux2][0]=1;
vec[aux2][vec[aux2][0]++]=aux1;
deg[aux2]=0;
}
else
if(aux1!=aux2)
vec[aux2][vec[aux2][0]++]=aux1;
}
for(i=1;i<=n;++i)
if(!deg[i])
{
++nrc;
NDFS(i);
}
printf("%d",nrc);
return 0;
}