Pagini recente » Cod sursa (job #104316) | Cod sursa (job #272379) | Cod sursa (job #1599549) | Cod sursa (job #722725) | Cod sursa (job #1856049)
#include <bits/stdc++.h>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct Nod
{
int info;
Nod *next;
};
Nod *listaNoduri[100001], *lastNod[100001], *nou, *p;
int n,m,x,y,coada[100001],prim,ultim,nr;
bool viz[100001];
void AdaugaNod(int x,int y)
{
if(listaNoduri[x]==NULL)
{
listaNoduri[x]=new Nod;
listaNoduri[x]->info=y;
listaNoduri[x]->next=NULL;
lastNod[x]=listaNoduri[x];
}
else
{
nou=new Nod;
nou->info=y;
nou->next=NULL;
lastNod[x]->next=nou;
lastNod[x]=nou;
}
}
void BFS(int nod)
{
viz[nod]=true;
prim=ultim=0;
coada[prim]=nod;
while(prim<=ultim)
{
for(p=listaNoduri[coada[prim]];p!=NULL;p=p->next)
if(!viz[p->info])
{
ultim++;
coada[ultim]=p->info;
viz[p->info]=true;
}
prim++;
}
}
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>x>>y;
AdaugaNod(x,y);
AdaugaNod(y,x);
}
for(int i=1;i<=n;i++)
if(!viz[i])
{
nr++;
BFS(i);
}
g<<nr;
return 0;
}