Pagini recente » Cod sursa (job #483635) | Cod sursa (job #2194483) | Cod sursa (job #876283) | Cod sursa (job #2302925) | Cod sursa (job #2139535)
#include <bits/stdc++.h>
using namespace std;
int vertices, edges, u, v, conexParts;
vector<int> adj[100001];
bool visited[100001];
void DFS(int start)
{
stack<int> s;
s.push(start);
while(!s.empty())
{
int current = s.top(); s.pop();
if(visited[current] == false)
{
for(int child : adj[current])
{
s.push(child);
}
visited[current] = true;
}
}
}
__attribute__((always_inline)) void read(int &num)
{
static char inBuffer[0x30D40];
static unsigned int p = 0x30D3F; num = 0x0;
while(inBuffer[p] < 0x30 | inBuffer[p] > 0x39)
{
++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
}
while(inBuffer[p] > 0x2F & inBuffer[p] < 0x3A)
{
num = num * 0xA + inBuffer[p] - 0x30;
++p != 0x30D40 || (fread(inBuffer, 0x1, 0x30D40, stdin), p = 0x0);
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
read(vertices); read(edges);
for(int i = edges; i; --i)
{
read(u), read(v);
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = vertices; i; --i)
{
visited[i] || (DFS(i), ++conexParts);
}
printf("%d", conexParts);
return 0;
}