Pagini recente » Cod sursa (job #1467852) | Cod sursa (job #164526) | Cod sursa (job #2367971) | Cod sursa (job #771637) | Cod sursa (job #2227456)
#include <cstdio>
#include <vector>
int vertices, edges, u, v, conexParts, visited[4096];
std :: vector<int> adj[100001];
void DFS(int current)
{
visited[current >> 5] |= 1 << (current & 0x1F);
for(int child : adj[current])
{
if(!(visited[child >> 5] & 1 << (child & 0x1F)))
{
DFS(child);
}
}
}
char buffer[20000000]; int p = -1;
__attribute__((always_inline)) int get_int()
{
int number = 0;
for(++p; buffer[p] > 47; ++p)
{
number = number * 10 + buffer[p] - 48;
}
return number;
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
fread(buffer, 1, 20000000, stdin);
vertices = get_int(), edges = get_int();
for(int i = edges + 1; --i;)
{
u = get_int(), v = get_int();
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = vertices + 1; --i;)
{
if(!(visited[i >> 5] & 1 << (i & 0x1F)))
{
DFS(i);
++conexParts;
}
}
printf("%d", conexParts);
return 0;
}