Pagini recente » Cod sursa (job #343005) | Cod sursa (job #1888691) | Cod sursa (job #90420) | Cod sursa (job #1319909) | Cod sursa (job #662843)
Cod sursa(job #662843)
#include <cstdio>
#include <list>
using namespace std;
int n,m,s;
int c[100002],v[100002];
list<int> l[100002];
void citire()
{
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d %d", &x, &y);
l[x].push_back(y);
l[y].push_back(x);
}
}
void bfs(int s)
{
c[1]=s;
v[s]=1;
int p,u;
p=1;u=1;
while(p<=u)
{
list<int>::iterator itl;
for(itl=l[c[p]].begin();itl!=l[c[p]].end();++itl)
if(v[*itl]==0)
{
u++;
c[u]=*itl;
v[*itl]=1;
}
p++;
}
}
int main()
{
freopen("dfs.in","rt",stdin);
freopen("dfs.out","wt",stdout);
scanf("%d %d", &n, &m);
citire();
int nrComp=0;
for(int i=1;i<=n;i++)
if(v[i]==0)
{
nrComp++;
bfs(i);
}
return 0;
}