Pagini recente » Cod sursa (job #466582) | Cod sursa (job #652782) | Cod sursa (job #619297) | Cod sursa (job #2252333) | Cod sursa (job #560557)
Cod sursa(job #560557)
#include<stdio.h>
#include<vector.h>
#include<queue.h>
#include<bitset>
#define dim 101000
#define pb push_back
using namespace std;
vector <int>v[dim];
bitset <dim> viz;
queue <int > q;
int n,m,x,y;
void read()
{
scanf("%d %d",&n,&m);
for(int i=1 ; i<=m;i++)
{
scanf("%d %d",&x ,&y);
v[x].pb(y);
v[y].pb(x);
}
}
inline void dfs(int x )
{
for(q.push(x) ; !q.empty(); q.pop())
{
x = q.front();
for(int i=0 ; i<v[x].size(); i++)
{
if ( viz [v[x][i]] == 0)
{
q.push(v[x][i]);
viz[v[x][i]] = 1 ;
}
}
}
}
void solve()
{
int nr =0;
for(int i=1 ; i<=n;i++)
{
if ( viz[i]==0)
{
nr++;
dfs(i);
}
}
printf("%d ", nr );
}
int main ()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
read();
solve();
return 0;
}