Pagini recente » Istoria paginii runda/oji20171112/clasament | proba123451 | Istoria paginii runda/summer_camp_4/clasament | Cod sursa (job #1793925) | Cod sursa (job #1025313)
#include <cstdio>
#include <vector>
using namespace std;
vector <int> a[100005];
int coada[110000],viz[100005],g[110000],prim,ultim,x,y,n,m,vfi,nr;
void dfs(int vf)
{
if(prim==ultim)
return;
for(int i=0;i<g[vf];i++)
{
if(viz[a[vf][i]]==0)
{
viz[a[vf][i]]=1;
coada[ultim]=a[vf][i];
ultim++;
}
}
prim++;
dfs(coada[prim]);
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
viz[i]=0;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
g[x]++;
g[y]++;
}
nr=0;
for(int i=1;i<=n;i++)
{
if(viz[i]==0)
{
ultim=1;
prim=0;
dfs(i);
nr++;
}
}
printf("%d",nr);
return 0;
}