Pagini recente » Cod sursa (job #1537497) | Cod sursa (job #1725884) | Cod sursa (job #2384897) | Cod sursa (job #1807365) | Cod sursa (job #369195)
Cod sursa(job #369195)
# include <fstream>
using namespace std;
struct nod {
int info;
nod*next;};
int n, v[100003], nrc;
nod *a[100003];
ofstream fout ("dfs.out");
void citire ()
{
int m;
ifstream fin ("dfs.in");
fin>>n>>m;
for (int i=1;i<=n;i++)
a[i]=NULL;
for (;m;--m)
{
int i, j;
fin>>i>>j;
nod *t;
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;
}
}
void bfs (int l, int nrc)
{
int k;
nod *st, *dr;
st=dr=new nod;
st->info=l;
st->next=NULL;
v[l]=nrc;
while (st)
{
k=st->info;
nod *p;
p=a[k];
while (p)
{
if (v[p->info]==0)
{
v[p->info]=nrc;
nod *q=new nod;
q->info=p->info;
q->next=NULL;
dr->next=q;
dr=q;
}
p=p->next;
}
p=st;
st=st->next;
delete p;
}
}
int main ()
{
citire ();
for (int i=1;i<=n;i++)
if (v[i]==0)
bfs(i, ++nrc);
fout<<nrc;
return 0;
}