Pagini recente » Cod sursa (job #1903259) | Cod sursa (job #2102882) | Cod sursa (job #2788355) | Cod sursa (job #1921328) | Cod sursa (job #2222520)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int NMAX = 100000;
vector<int> G[NMAX + 5];
vector<int> viz;
vector<int>::iterator it;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
void bfs(int u, int cc)
{
queue<int> q;
int v;
viz[u] = cc;
q.push(u);
while(!q.empty())
{
u = q.front(); q.pop();
for(it = G[u].begin(); it != G[u].end(); it++)
{
v = *it;
if(!viz[v])
{
viz[v] = cc; q.push(v);
}
}
}
}
int main()
{
int n, m, i, u, v, cc, j;
cin>>n>>m;
for(i = 1; i <= m; i++)
{
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
viz.assign(n+1, 0);
cc = 0;
for(i = 1; i <= n; i++)
{
if(!viz[i])
{
cc++;
bfs(i, cc);
}
}
cout<<cc<<"\n";
/*for(i = 1; i <= cc; i++)
{
for(j = 1; j <= n; j++)
if(viz[i] == cc)
cout<<j<<" ";
cout<<"\n";
}*/
return 0;
}