Pagini recente » Cod sursa (job #1686753) | Cod sursa (job #3188138) | Cod sursa (job #1608214) | Cod sursa (job #147428) | Cod sursa (job #943413)
Cod sursa(job #943413)
#include <fstream>
#include <queue>
#include <bitset>
using namespace std;
struct element
{
int indice;
element *next;
};
struct nod
{
element *cap;
element *coada;
}v[100005];
void insert(int x,int y)
{
element *p;
if(v[x].cap==NULL)
{
v[x].cap=new element;
v[x].coada=v[x].cap;
v[x].cap->indice=y;
v[x].cap->next=NULL;
}
else
{
p=new element;
p->indice=y;
p->next=NULL;
v[x].coada->next=p;
v[x].coada=p;
}
}
queue<nod> cd;
bitset<100005> frec;
void dfs(int nod)
{
cd.push(v[nod]);
frec[nod]=1;
element *p;
while(!cd.empty())
{
for(p=cd.front().cap;p!=NULL;p=p->next)
{
if(!frec[p->indice])
{
frec[p->indice]=1;
cd.push(v[p->indice]);
}
}
cd.pop();
}
}
int main()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m,i,x,y;
fin>>n>>m;
for(i=0;i<m;i++)
{
fin>>x>>y;
insert(x-1,y-1);
insert(y-1,x-1);
}
int cate=0;
for(i=0;i<n;i++)
{
if(!frec[i])
{
cate++;
dfs(i);
}
}
fout<<cate<<'\n';
fin.close();
fout.close();
return 0;
}