發表新討論
#16291: C求救


freedom501999@gmail.com (帥氣魔方生)

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [27.52.77.116] | 發表日期: 2018-12-16 01:28

 

#include <stdio.h>
#include <stdlib.h>
typedef struct NODE
{
	int n, rank;
	struct NODE *next;
	struct NODE *parent;
} node;
typedef node *link;
link Head[100001];
char run[100001];
void Delete_node(link ptr)
{
	link temp= ptr;
	while(temp->next!=NULL)
	{
		temp= temp->next;
		free(ptr);
		ptr=NULL;
		ptr=temp;
	}
	free(ptr);
	ptr=NULL;
}
void DFS_family(int val, link head[], char run[])
{
	link ptr;
	run[val]=1;
	ptr= head[val]->next;
	if(ptr!=NULL)
		head[ptr->n]->rank= head[val]->rank +1;
	while(ptr!=NULL)
	{
		if( run[ptr->n]==0)
			DFS_family(ptr->n, head, run);
		ptr=ptr->next;
		if(ptr!=NULL)
			head[ptr->n]->rank= head[ptr->parent->n]->rank;
	}
}
int main(void)
{
	int N, i, j, a, b;
	link newnode, ptr, ancestor;
	while(scanf("%d", &N)!=EOF)
	{
		for(i=0;i<N;i++)
		{
			run[i]=0;
			Head[i]=(link)malloc(sizeof(node));
			Head[i]->n = i;
			Head[i]->next= NULL;
			Head[i]->parent= NULL;
			Head[i]->rank=0;
		}
		for(i=1;i<N;i++)
		{
			scanf("%d %d", &a, &b);
			newnode=(link)malloc(sizeof(node));
			newnode->n =b;
			newnode->next= NULL;
			ptr=Head[a];
			while(ptr->next!=NULL)
				ptr= ptr->next;
			ptr->next= newnode;
			newnode->parent= ptr;
			Head[b]->parent= Head[a];
		}
		for(i=0;i<N;i++)
		{
			if(Head[i]->parent==NULL)
				ancestor= Head[i];
		}
		link start=ancestor;
		while(start->next->next== NULL)
			start= Head[start->next->n];
		DFS_family(start->n,Head, run);
		a=start->rank;
		for(i=0;i<N;i++)
		{
			if(Head[i]->rank > a)
			{
				a= Head[i]->rank;
				ptr= Head[i];
			}
		}
		run[ptr->n]++;
		b=start->rank;
		for(i=0;i<N;i++)
		{
			if(Head[i]->rank > b && run[i]==1)
				b= Head[i]->rank;
		}
		printf("%d\n", a+b);
		for(i=0;i<N;i++)
			Delete_node(Head[i]);
	}
	return 0;
}

結果如下

#0: 10% RE (SIGSEGV)

記憶體區段錯誤！
Segmentation fault (core dumped)

#1: 30% RE (SIGSEGV)

記憶體區段錯誤！
Segmentation fault (core dumped)

#2: 30% RE (SIGSEGV)

記憶體區段錯誤！
Segmentation fault (core dumped)

#3: 30% TLE (3s)

Segmentation fault (core dumped)

上網查了很多，還是不知道哪裡不合法

明明我自己的編譯器完全沒問題，送程式碼卻這樣

拜託大神指出我的問題吧

#16299: Re:C求救


qqrainbow (愛蜜莉雅)

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [36.236.91.202] | 發表日期: 2018-12-16 22:15

試試用陣列實作樹(adjacency list : http://www.csie.ntnu.edu.tw/~u91029/Graph.html)

以我的認知，malloc()是很慢的一個函式，https://www.slideshare.net/ccckmit/c-58955508

#17607: Re:C求救


a0905081237@gmail.com (哭哭饅頭)

b967. 4. 血緣關係 -- 2016年3月 apcs | From: [111.82.9.179] | 發表日期: 2019-04-27 16:33

 

#include 
#include 
typedef struct NODE
{
	int n, rank;
	struct NODE *next;
	struct NODE *parent;
} node;
typedef node *link;
link Head[100001];
char run[100001];
void Delete_node(link ptr)
{
	link temp= ptr;
	while(temp->next!=NULL)
	{
		temp= temp->next;
		free(ptr);
		ptr=NULL;
		ptr=temp;
	}
	free(ptr);
	ptr=NULL;
}
void DFS_family(int val, link head[], char run[])
{
	link ptr;
	run[val]=1;
	ptr= head[val]->next;
	if(ptr!=NULL)
		head[ptr->n]->rank= head[val]->rank +1;
	while(ptr!=NULL)
	{
		if( run[ptr->n]==0)
			DFS_family(ptr->n, head, run);
		ptr=ptr->next;
		if(ptr!=NULL)
			head[ptr->n]->rank= head[ptr->parent->n]->rank;
	}
}
int main(void)
{
	int N, i, j, a, b;
	link newnode, ptr, ancestor;
	while(scanf("%d", &N)!=EOF)
	{
		for(i=0;i<N;i++)
		{
			run[i]=0;
			Head[i]=(link)malloc(sizeof(node));
			Head[i]->n = i;
			Head[i]->next= NULL;
			Head[i]->parent= NULL;
			Head[i]->rank=0;
		}
		for(i=1;i<N;i++)
		{
			scanf("%d %d", &a, &b);
			newnode=(link)malloc(sizeof(node));
			newnode->n =b;
			newnode->next= NULL;
			ptr=Head[a];
			while(ptr->next!=NULL)
				ptr= ptr->next;
			ptr->next= newnode;
			newnode->parent= ptr;
			Head[b]->parent= Head[a];
		}
		for(i=0;i<N;i++)
		{
			if(Head[i]->parent==NULL)
				ancestor= Head[i];
		}
		link start=ancestor;
		while(start->next->next== NULL)//// while((start->next) != NULL && (start->next->next== NULL))
			start= Head[start->next->n];
		DFS_family(start->n,Head, run);
		a=start->rank;
		for(i=0;i<N;i++)
		{
			if(Head[i]->rank > a)
			{
				a= Head[i]->rank;
				ptr= Head[i];
			}
		}
		run[ptr->n]++;
		b=start->rank;
		for(i=0;i<N;i++)
		{
			if(Head[i]->rank > b && run[i]==1)
				b= Head[i]->rank;
		}
		printf("%d\n", a+b);
		for(i=0;i<N;i++)
			Delete_node(Head[i]);
	}
	return 0;
}

 

 


你的邊界條件出錯 , 如果指向next就空了,再指向一次next就會出錯 next-> next 那邊

ZeroJudge Forum