Pagini recente » Cod sursa (job #2189033) | Cod sursa (job #179269) | Cod sursa (job #703204) | Cod sursa (job #2539880) | Cod sursa (job #2139643)
#include <cstdio>
#include <vector>
#include <malloc.h>
struct node
{
unsigned int value; node *next;
};
node *adj[100001]; bool visited[100001];
void DFS(unsigned int current)
{
visited[current] = true;
for(node *child = adj[current]; child; child = child -> next)
{
if(!visited[child -> value]) DFS(child -> value);
}
}
#define SIZE 0xAAE6
__attribute__((always_inline)) void read(unsigned int &num)
{
static char inBuffer[SIZE];
static unsigned int p = ~-SIZE; num = 0x0;
while(inBuffer[p] < 0x30 | inBuffer[p] > 0x39)
{
++p != SIZE || (fread(inBuffer, 0x1, SIZE, stdin), p = 0x0);
}
while(inBuffer[p] > 0x2F & inBuffer[p] < 0x3A)
{
num = num * 0xA + inBuffer[p] - 0x30;
++p != SIZE || (fread(inBuffer, 0x1, SIZE, stdin), p = 0x0);
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
unsigned int vertices, edges;
read(vertices); read(edges);
for(unsigned int i = edges, u, v; i; --i)
{
read(u), read(v);
node *newbie = (node*)malloc(0x8);
newbie -> value = u;
newbie -> next = adj[v];
adj[v] = newbie;
newbie = (node*)malloc(0x8);
newbie -> value = v;
newbie -> next = adj[u];
adj[u] = newbie;
}
unsigned int conexParts;
for(unsigned int i = vertices; i; --i)
{
if(!visited[i])
{
DFS(i);
++conexParts;
}
}
printf("%d", conexParts);
return 0x0;
}