Pagini recente » Cod sursa (job #1863170) | Cod sursa (job #1333334) | Cod sursa (job #2010762) | Cod sursa (job #1849026) | Cod sursa (job #423232)
Cod sursa(job #423232)
#include <stdio.h>
struct node
{
int value;
node *link;
};
node* nodes[100001];
int v[100001];
void cleanup(node *n)
{
if(n == NULL)
return;
cleanup(n->link);
delete n;
}
void dfs(int i, int c)
{
v[i] = c;
node* t = nodes[i];
while(t != NULL)
{
if(v[t->value] == 0)
{
dfs(t->value, c);
}
t = t->link;
}
}
int main(void)
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int n, m;
int c = 1;
int i;
scanf("%d %d", &n, &m);
for(i=0;i<n;++i)
{
nodes[i] = NULL;
v[i] = 0;
}
for(i=0;i<m;++i)
{
int a,b;
scanf("%d %d", &a, &b);
node* n1 = new node;
n1->value = b;
n1->link = nodes[a];
nodes[a] = n1;
node* n2 = new node;
n2->value = a;
n2->link = nodes[b];
nodes[b] = n2;
}
for(i=0;i<n;++i)
{
if(v[i] == 0)
{
dfs(i, c);
c++;
}
}
for(i=0;i<n;++i)
{
cleanup(nodes[i]);
}
printf("%d\n",c-1);
return 0;
}