80分,8,9两个点WA掉了求救
查看原帖
80分,8,9两个点WA掉了求救
318285
战斗天使楼主2020/4/27 08:54
#include <iostream>
#include <cstring>
#include <queue>
#include <map>
#include <algorithm>
#define  Max 10000
using namespace std;
struct Node
{
    int left;
    int right;
};
map<int ,Node> t;
bool flag[Max];
int res=0;
void dfs(int n,int level,int y1,int y2);
int get_depth(int n);
int get_width(int n);
    int main()
    {
        int n,x1,x2;
        cin>>n;
        memset(flag, false, sizeof(flag));
        for(int i=1;i<=n-1;i++)
        {
            cin>>x1>>x2;
            if(!flag[x1])
            {
                t[x1].left=x2;
                flag[x1]=true;
            }
            else if(flag[x1])
            {
                t[x1].right=x2;
            }
        }
        int y1,y2;
        cin>>y1>>y2;
        dfs(1,0,y1,y2);
        cout<<get_depth(1)<<endl;
        cout<<get_width(1)<<endl;
        cout<<res<<endl;
        return 0;
    }

    void dfs(int n,int level,int y1,int y2)//求节点之间的距离
    {
        if(n==0)
        {
            return ;
        }
        if(n==y1||n==y2)
        {
            if(y1==y2)
            {
                res+=level*2+level;
                return ;
            }
           else if(n==y1)
            {
                res+=level*2;
            }
            else
            {
                res+=level;
            }
        }
        dfs(t[n].left,level+1,y1,y2);
        dfs(t[n].right,level+1,y1,y2);
    }

    int get_depth(int n)
    {
        if(n==0)
        {
            return 0;
        }
        int left=get_depth(t[n].left);
        int right=get_depth(t[n].right);
        return max(left,right)+1;
    }


    int get_width(int n)
    {
        queue<int > que;
        que.push(n);
        int MAX=1;//宽度最小为1
        int num=que.size();
        while(num)
        {
            while(num--)
            {
                int f=que.front();
                que.pop();
                if(t[f].left!=0)
                {
                    que.push(t[f].left);
                }
                if(t[f].right!=0)
                {
                    que.push(t[f].right);
                }
            }
            num=que.size();
            MAX=max(MAX,num);
        }
        return MAX;
    }
2020/4/27 08:54
加载中...