Pagini recente » Cod sursa (job #2325245) | Cod sursa (job #1899872) | Cod sursa (job #2688027) | Cod sursa (job #1880762) | Cod sursa (job #698472)
Cod sursa(job #698472)
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct tnod
{
tnod *first,*last,*next,*haspar;
int val,chk;
} *a[100005],*p1,*p2,x1,x2;
int x,y,n,m,nb,i;
void link(tnod *a, tnod *b);
int dfs(tnod *p);
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
x1=new tnod; x2=new tnod;
p1=&x1; p1->val=x; p1->chk=0;
p1->first=NULL; p1->last=NULL; p1->next=NULL; p1->haspar=NULL;
p2=&x2; p2->val=y; p2->chk=0;
p2->first=NULL; p2->last=NULL; p2->next=NULL; p2->haspar=NULL;
int ok1=0,ok2=0;
if(a[x]==NULL) {a[x]=p1; ok1=1;}
if(a[y]==NULL) {a[y]=p2; ok2=1;}
if(ok1 || ok2) link(a[x],a[y]);
}
int j=1;
while(j<=n)
{
nb++; if(a[j]!=NULL) dfs(a[j]);
while(a[j]->chk==1) j++;
}
g<<nb;
g.close();
f.close();
return 0;
}
void link(tnod *a, tnod *b)
{
if(a->first==NULL) a->first=b;
if(b->first==NULL) b->first=a;
if(b->last!=NULL) {b->last->next=a; b->last->haspar=b;}
if(a->last!=NULL) {a->last->next=b; a->last->haspar=a;}
b->last=a; a->last=b;
if(b->last!=b->first) a->haspar=b;
if(a->last!=a->first) b->haspar=a;
}
int dfs(tnod *p)
{
if(p==NULL) return 0;
p->chk=1;
tnod *t=p->first;
if(t==NULL) return 0;
while(t!=NULL)
{
if(t->chk==0) dfs(t);
t=t->next;
}
return 1;
}