Pagini recente » Cod sursa (job #750369) | Cod sursa (job #562684) | Cod sursa (job #3169872) | Cod sursa (job #1872690) | Cod sursa (job #839481)
Cod sursa(job #839481)
#include<fstream>
#include<vector>
#include<queue>
#define NMAX 100009
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");
int n, m, nod_a, nod_b, viz[NMAX];
queue<int>q;
vector<int>x[NMAX];
inline void citire();
inline void dfs(int);
int main()
{
citire();
int nr_cp = 0;
for(int i = 1; i <= n; ++i)
if(!viz[i])
{
nr_cp++;
dfs(i);
}
g<<nr_cp<<'\n';
g.close();
return 0;
}
inline void citire()
{
f>>n>>m;
for(int i = 1; i <= m; ++i)
{
f>>nod_a>>nod_b;
x[nod_a].push_back(nod_b);
x[nod_b].push_back(nod_a);
}
f.close();
}
inline void dfs(int k)
{
q.push(k);
viz[k] = 1;
while(!q.empty())
{
k = q.front(); q.pop();
vector<int>::iterator it;
for(it = x[k].begin(); it != x[k].end(); ++it)
if(!viz[(*it)])
{
viz[(*it)] = 1;
q.push((*it));
}
}
}