Pagini recente » Clasament alegem | Cod sursa (job #1379522) | Cod sursa (job #2211884) | Cod sursa (job #1572601) | Cod sursa (job #216106)
Cod sursa(job #216106)
// dfs-componente conexe int*[]
#include <cstdio>
#define N 100001
int M[2*N][2],len[N], n, m;
int *a[N];
bool use[N];
void read()
{
freopen("dfs.in","r",stdin);
scanf("%d %d\n", &n, &m);
int p, q,i;
for(i=1;i<=m;++i)
{
scanf("%d %d\n", &p, &q);
M[i][0]=p;
M[i][1]=q;
++len[p];
++len[q];
}
for(i=1;i<=n;++i)
a[i]=new int[len[i]+2],len[i]=0;
for(i=1;i<=m;++i)
{
p=M[i][0];
q=M[i][1];
a[p][len[p]++]=q;
a[q][len[q]++]=p;
}
for(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;
}