求助一下,不知道哪里写错了(样例过了,自己也造了一组数据)
查看原帖
求助一下,不知道哪里写错了(样例过了,自己也造了一组数据)
474838
PzbBUAAer楼主2022/12/13 11:30

求教 初学数据结构,不知道哪里写错了

构造表时已经排序了,但WA第一个点 MLE后面四个

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define datatype long long
struct edgenode//边结点 
{
//	int weight;
	edgenode* next;
	int no;//入边顶点编号 
};
struct vertexnode//顶点结点 
{
	int no;
	edgenode* head;
};

vertexnode* insert(vertexnode* list, int start, int end)//插入排序 
{
	edgenode* temp = list[start-1].head;//当前节点 
	edgenode* pretemp=NULL;//前驱节点 
	for(;temp;temp=temp->next)//找到插入位置 
	{
		if(temp->no > end)
		{
			if(pretemp==NULL)//头节点插入
			{
				pretemp = new edgenode;
				pretemp->next = temp;
				pretemp->no = end;
				list[start-1].head = pretemp;
			}
			else//中间节点插入 
			{
				edgenode* newone = new edgenode;
				newone->next = temp->next;
				newone->no = end;
				temp->next = newone;
			}
			return list;
		}
		pretemp = temp;
	}
	//只能插在末尾 
	temp = new edgenode;
	temp->no = end;
	temp->next = NULL;
	if(pretemp) 
		pretemp->next = temp;
	else
		list[start-1].head = temp;
		//当前为空表 
	return list; 
}
void *_DFS(vertexnode* list, int startpos, int* visit)
{
	if(visit[startpos-1]==0)
		{
			//访问 
			visit[startpos-1]=1;
			printf("%d ",startpos);
		}
	for(edgenode* temp = list[startpos-1].head;temp;temp=temp->next)
	{
//		printf("visit%d ,",temp->no);
		if(visit[(temp->no)-1])//访问过了
			;
		else
			{
//				printf("visit%d ,",temp->no);
				_DFS(list, temp->no, visit);
			}
	}
}
void *DFS(vertexnode* list, int startpos, int len)
{
	int *visit = new int [len];
	memset(visit, 0, sizeof(int)*len);
	int top = startpos-1;
	for(;top<len;top++)
	{
		if(visit[top])//访问过
			continue;
		_DFS(list, top+1, visit); 
	}
	delete[] visit;
}

void *_BFS(vertexnode* list, int startpos, int* visit, int len)
{
	int * linestack = new int [15000];
	memset(linestack, 0, sizeof(int)*(15000));
	{
		int h=0,t=0;
		linestack[t] = startpos;
		for(;h<=t;h++)
		{
			//访问队首元素 
			if(visit[linestack[h]-1]==0)
			{
				visit[linestack[h]-1] = 1;
				printf("%d ",list[linestack[h]-1].no); 
			}
			//将其边入队
			for(edgenode* temp = list[linestack[h]-1].head; temp; temp=temp->next)
			{	//printf(" visit%d ",temp->no);
				if(visit[(temp->no)-1]==0)//没访问过 
					linestack[++t] = temp->no; 
			}
		}
	}
	delete[] linestack;
}
void *BFS(vertexnode* list, int startpos, int len)
{
	int *visit = new int [len];//建立禁忌箓,以便历遍所有连通分量 
	memset(visit, 0, sizeof(int)*len);
	int top = startpos-1;
	for(;top<len;top++)
	{
		
		if(visit[top])//访问过
			continue;
		else
			{
			_BFS(list, top+1, visit, len);
			}
	}
	delete[] visit;
}
//写图的DFS和BFS 
int main()
{
	int n,m;//10^5,10^6;
	scanf("%d%d",&n,&m);
	vertexnode* list = new vertexnode [n];
	for(int i=0;i<n;i++)
	{
		list[i].head = 0;
		list[i].no = i+1;
	}
	for(int i=0;i<m;i++)
	{
		int start, end;
		scanf("%d%d",&start, &end);
		list = insert(list, start, end);//插入排序,构造邻接表 
										//确保构造邻接表时从标号由小到大 
	}
	DFS(list, 1, n);
	printf("\n");
	BFS(list, 1, n);
	return 0;
 } 
 /*
 7 9
 1 3
 3 5
 3 4
 3 7
 4 6
 5 6
 7 6
 6 2
 2 1
 */
2022/12/13 11:30
加载中...