Pagini recente » Cod sursa (job #127722) | Cod sursa (job #1266853) | Cod sursa (job #1111145) | Cod sursa (job #1504269) | Cod sursa (job #897700)
Cod sursa(job #897700)
#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, f, ok;
for (i=1; i<=n; i++)
if (v[i]==0)
{
k++;
f=1;
v[i]=k;
st[f]=i;
while (f>0)
{
ok=0;
for (p=prim[st[f]]; p; p=p->next)
if (!v[p->info])
{
v[p->info]=k;
st[++f]=p->info;
ok=1;
}
if (!ok)
f--;
}
}
out<<k;
return 0;
}