Pagini recente » Cod sursa (job #2735483) | Cod sursa (job #2172906) | Cod sursa (job #2887220) | Cod sursa (job #662240) | Cod sursa (job #1169596)
#include <fstream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
int N, M;
vector<int> Graph[100010];
queue<int> Q;
bitset<100010> witness;
int main()
{
int i, j, x, y, rez = 0, node;
vector<int>::iterator it;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
fin >> N >> M;
for (i = 0; i < M; ++i)
{
fin >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
for (i = 1; i <= N; ++i)
{
if (!witness[i])
{
++rez;
witness[i] = true;
Q.push(i);
while(!Q.empty())
{
node = Q.front();
Q.pop();
for (it = Graph[node].begin(); it != Graph[node].end(); ++it)
{
if (!witness[*it])
{
witness[*it] = true;
Q.push(*it);
}
}
}
}
}
fout << rez << '\n';
fout.close();
return 0;
}