Pagini recente » Cod sursa (job #1647389) | Cod sursa (job #3288501) | Cod sursa (job #3184156) | Cod sursa (job #1678655) | Cod sursa (job #698419)
Cod sursa(job #698419)
#include <fstream>
#include <mem>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct tnod
{
tnod *first,*last,*next,*haspar;
int val,chk;
};
tnod *a[100001],*p1,*p2;
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;
p1=new tnod; p1->val=x; p1->chk=0;
p1->first=NULL; p1->last=NULL; p1->next=NULL; p1->haspar=NULL;
p2=new tnod; 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]);
}
for(i=1;i<=n;i++)
if(a[i]==NULL)
{
p1=new tnod; p1->val=i; p1->chk=0;
p1->first=NULL; p1->last=NULL; p1->next=NULL; p1->haspar=NULL;
a[i]=p1;
}
int j=1;
while(j<=n)
{
nb++; 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;
}