欧拉路.txt

图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!

#include <stdio.h>                //圈套圈算法
#include <string.h>
#include <malloc.h>
#include <algorithm>
#define N 100010
#define DEF (struct point *)malloc(sizeof(struct point))
#define ST struct point
#define NULL 0
using namespace std;

struct line
{
 int beg;
 int end;
}road[N]={0};

struct point
{
 int data;
 struct point *next;
}*head,*mide,*midf,*end,*midd;

int cou=1,check[N]={0};

bool cmp(const line &a,const line &b)
{
 if(a.beg<b.beg) return true;
 return false;
}

void init()
{
 head=DEF;mide=DEF;midf=DEF;end=DEF;midd=DEF;
 head->data=NULL;
 head->next=NULL;
 midd=head;
 midf=mide;
 end=head;
}

void cle()
{
 ST *use;
 use=DEF;
 midf=mide=use;
}

void insert(int n)
{
 ST *use;
 use=DEF;
 use->next=NULL;
 midd->data=n;
 midd->next=use;
 midd=use;
}

void creat(int n)
{
 ST *use;
 use=DEF;
 use->next=NULL;
 use->data=n;
 mide->next=use;
 mide=use;
}

void add()
{
 mide->next=end->next->next;
 end->next->next=midf->next;
 end=end->next;
 cle();
}

void pt()
{
 ST *p;
 p=head->next;
 while(p->next!=NULL)
 {
  printf("%d\n",p->data);
  p=p->next;
 }
}

void addedge(int a,int b)
{
 road[cou].beg=a;
 road[cou].end=b;
 road[cou+1].beg=b;
 road[cou+1].end=a;
 cou+=2;
}

void table()
{
 int i;
 check[road[1].beg]=1;
 for(i=2;i<cou;i++)
 {
  if(road[i].beg!=road[i-1].beg) check[road[i].beg]=i;
 }
 check[road[i-1].beg+1]=i;
}

void solve()
{
 int mid,a=1,b,c,num=0,d=2;
 init();
 insert(0);
 insert(a);
 while(1)
 {
  b=a;
  while(1)
  {
   mid=check[b];
   if(road[mid].beg!=b) {end=end->next;goto end;}
   c=road[mid].end;
   num++;
   check[b]++;
   creat(c);
   if(c==a) break;
   b=c;
  }
  add();
end:
  a=end->next->data;
  if(num==cou-1) break ;
 }
 pt();
}

int main()
{
 int n,m,i,a,b;
 scanf("%d %d",&n,&m);
 for(i=1;i<=m;i++)
 {
  scanf("%d %d",&a,&b);
  addedge(a,b);
 }
 
 sort(road+1,road+cou,cmp);

 table();
 solve();
}