Pagini recente » Cod sursa (job #2185111) | Cod sursa (job #1874043) | Cod sursa (job #2185123) | Cod sursa (job #1954222)
// DFSCompConexe.cpp : Defines the entry point for the console application.
//
#include <stdio.h>
#include <string.h>
struct link *nodes;
struct link
{
unsigned int v;
link *next;
};
void backtrack(link *node)
{
if (!node->v)
{
node->v = -1;
link *p = node->next;
while (p)
{
backtrack(&nodes[p->v]);
p = p->next;
}
}
}
void read(link *node, unsigned int m, const unsigned int n)
{
unsigned int i, a, b;
struct link *p[100000], *new_link;
for (i = 0; i < n; ++i)
{
p[i] = node + i;
}
for (i = 0; i < m; ++i)
{
scanf("%u %u", &a, &b);
--a;
--b;
new_link = new link;
new_link->v = b;
new_link->next = 0;
p[a]->next = new_link;
p[a] = new_link;
new_link = new link;
new_link->v = a;
new_link->next = 0;
p[b]->next = new_link;
p[b] = new_link;
}
}
int main(int argc, char* argv[])
{
unsigned int n, m, i, cc = 0;
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%u %u", &n, &m);
nodes = new link[n];
memset(nodes, 0x00, sizeof(*nodes)*n);
read(nodes, m, n);
for (i = 0; i < n; ++i)
if (!nodes[i].v)
{
backtrack(&nodes[i]);
++cc;
}
printf("%u", cc);
return 0;
}