1943019_ac_888ms_1484k.cpp

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

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MaxVertexNum 1002

bool mark;
bool visited[MaxVertexNum];
bool a[MaxVertexNum][MaxVertexNum];
typedef int VertexType;
typedef struct node
{
	int adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct ALGraph
{
	AdjList adjlist;
}Graphic;

void dfs(Graphic *G, int v1, int v2)
{
	EdgeNode *s;

	s = G->adjlist[v1].firstedge;
	visited[v1] = 1;
	if(a[v1][v2] == 1)
		mark = 1;
	while(s)
	{
		if(mark)
			return ;
		if(visited[s->adjvex] == 0)
			dfs(G,s->adjvex,v2);
		s = s->next;
	}
}

void delete_vex(Graphic *G,int v1,int v2)
{
	EdgeNode *s;

	a[v1][v2] = a[v2][v1] = 0;
	s = G->adjlist[v1].firstedge;
	if(s->adjvex == v2)
	{
		G->adjlist[v1].firstedge = s->next;
		goto k;
	}
	while(s)
	{
		if(s->next->adjvex == v2)
		{
			s->next = s->next->next;
			break;
		}
		else
			s = s->next;
	}
k: ;
   s = G->adjlist[v2].firstedge;
   if(s->adjvex == v1)
   {
	   G->adjlist[v2].firstedge = s->next;
	   return ;
   }
   while(s)
	{
		if(s->next->adjvex == v1)
		{
			s->next = s->next->next;
			break;
		}
		else
			s = s->next;
	}
}
void insert_vex(Graphic *G,int v1,int v2)
{
	EdgeNode *s;

	a[v1][v2] = a[v2][v1] = 1;
	s = (EdgeNode *)malloc(sizeof(EdgeNode));
	s->adjvex = v1;
	s->next = G->adjlist[v2].firstedge;
	G->adjlist[v2].firstedge = s;
	s = (EdgeNode *)malloc(sizeof(EdgeNode));
	s->adjvex = v2;
	s->next = G->adjlist[v1].firstedge;
	G->adjlist[v1].firstedge = s;
}
void Output(Graphic *G, int N)
{
	int i;
	EdgeNode *s;

	for(i = 1; i <= N; i++)
	{
		s = G->adjlist[i].firstedge;
		printf("%d-",i);
		while(s)
		{
			printf("%d-",s->adjvex);
			s = s->next;
		}
		printf("\n");
	}
}
void CreateGraphic(Graphic *G)
{
	char com;
	int N, Q, v1, v2;
	int i, j, k;

	scanf("%d%d",&N,&Q);
	for(i = 0; i <= N; i++)
		G->adjlist[i].firstedge = NULL;
	for(i = 0; i <= N; i++)
		for(j = 0; j <= N; j++)
			a[i][j] = 0;
	for(i = 0; i < Q; i++)
	{
		getchar();
		scanf("%c%d%d",&com,&v1,&v2);
	
		if(v1 == v2)
		{
			if(com == 'Q')
				printf("Y\n");
			continue;
		}
		switch(com)
		{
		case 'Q': mark = 0;memset(visited,0,sizeof(visited));dfs(G,v1,v2);if(mark) printf("Y\n"); else printf("N\n");break;
		case 'D': delete_vex(G,v1,v2);break;
		case 'I': insert_vex(G,v1,v2);break;
		}
	/*	for(j = 0; j < N; j++)
		{
			for(k = 0; k < N; k++)
				printf("%d ",a[j+1][k+1]);
			printf("\n");
		}
		Output(G,N);*/
	}
}

int main()
{
	Graphic Create;
	CreateGraphic(&Create);
	return 1;
}