Pagini recente » Cod sursa (job #1182174) | Cod sursa (job #1792038) | Cod sursa (job #1076705) | Cod sursa (job #974117) | Cod sursa (job #560546)
Cod sursa(job #560546)
#include<stdio.h>
#include<vector.h>
#include<algorithm>
#include<bitset>
#include<queue>
using namespace std;
#define dim 101000
struct nod
{
int el;
nod *next;
}*liste[dim];
int n,m;
bitset<dim> viz;
queue<int>q;
inline void add(int x , int y )
{
nod *p=new nod;
p->el=y;
p->next=liste[x];
liste[x]=p; return;
}
void read()
{
int x,y;
scanf("%d %d",&n,&m);
for(int i=1 ; i<=m;i++)
{
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
}
inline void bf(int x)
{
nod *p=liste[x];
for(q.push(x) ; !q.empty(); q.pop())
{
x = q.front();
p=liste[x];
while (p)
{
if ( viz[p->el]==0 )
{
viz[p->el]=1;
q.push(p->el);
}
p=p->next;
}
}
}
void solve ()
{
int nr=0;
for(int i=1 ; i<=n;i++)
{
if ( viz[i] == 0 )
{
bf (i);
nr++;
}
}
printf("%d ",nr);
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
read();
solve();
return 0;
}