Pagini recente » Cod sursa (job #35877) | Cod sursa (job #1877951) | Cod sursa (job #367650) | Cod sursa (job #744934) | Cod sursa (job #369218)
Cod sursa(job #369218)
#include<fstream>
#include<iostream>
using namespace std;
#define max 100001
struct nod{
int info;
nod* next;
};
int n,v[max],nrc;
nod *a[max];
void read()
{
int m,i,j;
ifstream fin("dfs.in");
fin>>n>>m;
for(int i=1;i<=n;i++)
a[i]=NULL;
for(;m;--m)
{
fin>>i>>j;
nod *t=new nod;
t->info=j;
t->next=a[i];
a[i]=t;
t=new nod;
t->info=i;
t->next=a[j];
a[j]=t;
}
fin.close();
}
void dfs(int i)
{
v[i]=1;
nod *t;
for(t=a[i];t;t=t->next)
if(v[t->info]==0)
{
//t[k]=i;
dfs(t->info);
}
}
void bfs (int i)
{
nod *st, *dr;
st=dr=new nod;
st->info=i;
st->next=NULL;
v[i]=1;
while (st)
{
i=st->info;
nod *t;
t=a[i];
while (t)
{
if (v[t->info]==0)
{
v[t->info]=1;
nod *q=new nod;
q->info=t->info;
q->next=NULL;
dr->next=q;
dr=q;
}
t=t->next;
}
t=st;
st=st->next;
delete t;
}
}
int main()
{
read();
int nrc=0;
for(int i=1;i<=n;i++)
if(v[i]==0)
bfs(i),nrc++;
FILE *fout=fopen("dfs.out","w");
fprintf(fout,"%d",nrc);
return 0;
}