Pagini recente » Cod sursa (job #1419672) | Cod sursa (job #407015) | Cod sursa (job #1619256) | Cod sursa (job #2732607) | Cod sursa (job #897222)
Cod sursa(job #897222)
#include <fstream>
using namespace std;
struct nod {
int info;
nod *next;} *prim[100007], *aux, *p;
int st[100007], v[100007];
int main()
{
int n, m;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
in>>n>>m;
int i, a, b;
for (i=1; i<=m; i++)
{
in>>a>>b;
aux=new nod;
aux->info=a;
aux->next=prim[b];
prim[b]=aux;
aux=new nod;
aux->info=b;
aux->next=prim[a];
prim[a]=aux;
}
int k=0, l=1, f=1;
st[1]=1;
for (i=1; i<=n; i++)
if (v[i]==0)
{
k++;
f=1;
v[i]=k;
st[f]=i;
while (f>0)
{
for (p=prim[st[f]]; p; p=p->next)
if (!v[p->info])
{
v[p->info]=k;
st[++f]=p->info;
}
f--;
}
}
out<<k;
return 0;
}