Pagini recente » Cod sursa (job #794606) | Cod sursa (job #1402780) | Cod sursa (job #2089507) | Cod sursa (job #2168898) | Cod sursa (job #216115)
Cod sursa(job #216115)
// dfs-componente conexe int*[] cu realloc
#include <cstdio>
#include <cstdlib>
#define N 100001
int *a[N];
int n, m;
bool use[N];
int len[N];
void read()
{
freopen("dfs.in","r",stdin);
int p, q;
scanf("%d %d\n", &n, &m);
for(int i=1;i<=n;++i) a[i]=new int[2];
while(m--)
{
scanf("%d %d\n", &p, &q);
a[p]=(int*)realloc(a[p], sizeof(int)*(len[p]+2));
a[q]=(int*)realloc(a[q], sizeof(int)*(len[q]+2));
a[p][len[p]++]=q;
a[q][len[q]++]=p;
}
for(int i=1;i<=n;++i) a[i][len[i]]=0;
}
inline void dfs(int n)
{
use[n]=1;
for(int *i=a[n]; *i; ++i)
if(!use[*i])
dfs(*i);
}
int main()
{
read();
int i, sol=0;
for(i=1;i<=n;++i)
if(!use[i])
{
++sol;
dfs(i);
}
freopen("dfs.out","w",stdout);
printf("%d\n", sol);
return 0;
}