求助,看了十几遍没看出问题......
查看原帖
求助,看了十几遍没看出问题......
127925
Kio_楼主2020/8/22 12:02

RT,上洛谷ide提示是“超出内存限制”......

代码看了十几遍了,似乎不会爆栈,数组也不会

#include<cstdio>
//#include<vector>
using namespace std;
struct node
{
	int d=1,l=0,r=0,p;
}tree[120];
int n;
int maxd;
int wide[120];//用于判最大宽度
bool pd[120];//用于判断tarjan算法中是否已遍历过某节点
int j[120];//并查集
int find(int x)
{
	if(x!=j[x])j[x]=find(x);
	return j[x]; 
}
void _union(int x,int y)
{
	j[find(x)]=find(y);
}

int xgoal1,xgoal2;//分别为题目中的最后两个输入

void tarjan(int x)
{
	if(flag==1)return;//已找到目标节点就直接返回
	if(tree[x].l)tarjan(tree[x].l);//递归左右子树
	if(tree[x].r)tarjan(tree[x].r);
	
	pd[x]=1;//已走过

//	if(pd[tree[x].l]==1&&pd[tree[x].r]==1)
//	{
//		if(x==1)return;
		if((x==xgoal2&&pd[xgoal1]==1) || (x==xgoal1&&pd[xgoal2]==1))//若已走到目标节点(此时当前节点的左右子树都递归完毕)
		{
			flag=1;
			printf("%d", (tree[find(xgoal1)].d - tree[xgoal1].d) * 2 + tree[xgoal2].d - tree[find(xgoal1)].d);//输出
			return;
		}
//	}
	
	if(x!=1)_union(x,tree[x].p);//合并
}
int main()
{
	pd[0]=1;
	wide[1]=1;
	scanf("%d",&n);
	
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		if(tree[a].l) tree[a].r=b;
		else tree[a].l=b;
        
		tree[b].p=a; 
        
		if(tree[b].d <= tree[a].d) tree[b].d = tree[a].d + 1;
		else tree[a].d=tree[b].d+1;
		
		wide[tree[b].d]++;
		
		if(tree[a].d>maxd)maxd=tree[a].d;
		if(tree[b].d>maxd)maxd=tree[b].d;
	}
	
	for(int i=1;i<=n;i++)j[i]=i;
	
	int maxw=0;
	for(int i=1;i<=100;i++)
	{
		if(wide[i]>maxw)maxw=wide[i];
	}

	
//	printf("%d %d\n",tree[a].d,tree[b].d);
	printf("%d\n%d\n",maxd,maxw);	
//	printf("-------%d %d--------\n",tree[1].l,tree[1].r);
	scanf("%d %d",&xgoal1,&xgoal2);
	tarjan(1);
	return 0;
}

求大佬指教!QwQ

2020/8/22 12:02
加载中...