Pagini recente » Cod sursa (job #1227185) | test111 | gigi_becali | Cod sursa (job #1391160) | Cod sursa (job #216102)
Cod sursa(job #216102)
// dfs- componente conexe...cu liste inlantuite
#include <cstdio>
#define N 100001
struct nod { int x; nod *n;};
nod *a[N];
int n, m;
bool use[N];
void read()
{
freopen("dfs.in","r",stdin);
scanf("%d %d\n", &n, &m);
nod *t;
int p, q;
while(m--)
{
scanf("%d %d\n", &p, &q);
t=new nod;
t->x=q;
t->n=a[p];
a[p]=t;
t=new nod;
t->x=p;
t->n=a[q];
a[q]=t;
}
}
inline void dfs(int n)
{
use[n]=1;
for(nod *i=a[n]; i; i=i->n)
if(!use[i->x])
dfs(i->x);
}
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;
}