2169785_ac_980ms_6352k.cpp

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <stdlib.h>
# define MAXV 20001
# define INIT (Vex *)malloc(sizeof(Vex))
# define MAXE 100001

int n;
long m;
int visited[MAXV];
int edge[MAXE];
int d[MAXV];
int id[MAXV];
typedef struct node
{
	int adj;
	int edge_id;
	struct node *next;
}Vex;

typedef struct Node
{
	Vex *head;
	int no;
}Adj;

typedef struct NODE
{
	Adj adjlist[MAXV];
}Graphic;

void init(Graphic *G)
{
	int i;
	
	for(i = 0; i < n; i++)
	{
		visited[i] = 0;
		G->adjlist[i].head = INIT;
		G->adjlist[i].head->next = NULL;
		d[i] = 0;
		G->adjlist[i].no = i;
	}
}

int cmp(const void *a,const void *b)
{	
	Adj *aa = (Adj *)a;
	Adj *bb = (Adj *)b;
	
	return id[aa->no]-id[bb->no];
}

void insert(int v1,int v2,Graphic *G,int edge_no)
{
	Vex *s;
	
	s = INIT;
	s->adj = v2;s->edge_id = edge_no;
	s->next = G->adjlist[v1].head->next;
	G->adjlist[v1].head->next = s;
	s = INIT;
	s->adj = v1;s->edge_id = edge_no;
	s->next = G->adjlist[v2].head->next;
	G->adjlist[v2].head->next = s;
	d[v2]++;d[v1]++;
}

void input(Graphic *G)
{
	long i;
	int v1, v2;
	
	scanf("%d%ld",&n,&m);
	init(G);
	for(i = 0; i < m; i++)
	{
		edge[i] = 1;
		scanf("%d%d",&v1,&v2);
		insert(v1-1,v2-1,G,i);
	}
}

void output(Graphic G)
{
	int i;
	Vex *s;
	
	for(i = 0; i < n; i++)
	{
		s = G.adjlist[i].head;
		printf("%d",G.adjlist[i].no);
		while(s->next)
			{
				printf("-%d",s->next->adj);
				s = s->next;
			}
		printf("\n");
	}
}

void dfs(Graphic *G,int v,int no)
{
	Vex *s;
	
	visited[v] = 1;
	id[v] = no;
	s = G->adjlist[v].head;
	while(s->next)
	{
		if(visited[s->next->adj]==0)
			dfs(G,s->next->adj,no+1);
		s = s->next;
	}
}

void solve(Graphic *G)
{
	int i, D;
	int flag;
	Vex *s;
	
	for(i = n-1; i >= 0; i--)
	{
		if(d[G->adjlist[i].no]<2)
			continue;
		flag = 1;
		s = G->adjlist[i].head;
		D = d[G->adjlist[i].no];
		while(s->next)
		{
			if(D%2&&id[G->adjlist[i].no]==id[s->next->adj]+1)
				{
					s = s->next;
					continue;
				}
			if(edge[s->next->edge_id])
			{
				if(flag)
				{
					d[G->adjlist[i].no]--;
					d[s->next->adj]--;
					printf("%d %d ",s->next->adj+1,G->adjlist[i].no+1);
					flag = 0;
				}
				else
				{
					d[G->adjlist[i].no]--;
					d[s->next->adj]--;
					printf("%d\n",s->next->adj+1);
					flag = 1;
				}
				edge[s->next->edge_id] = 0;
			}
			s = s->next;
		}
	}
}

int main()
{
	int i;
	Graphic G;

	input(&G);
	dfs(&G,0,0);
	qsort(G.adjlist,n,sizeof(G.adjlist[0]),cmp);
	solve(&G);
	return 1;
}