求助,简单代码为什么会死循环

回复帖子

@变成一名fw 2020-05-22 21:25 回复

在做树的重心模板,然后输入的时候死循环了,发现是

    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        es[x].push_back(y);
        es[y].push_back(x);

这里的问题,这样写不对吗

求助/kel

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,p[MAXN],sz[MAXN],f[MAXN],g[MAXN];
//p[i]记录i的父亲,sz[i]记录以i为根的子树大小 f[i]表示儿子为根的最大子树的大小,g[i]是删除i后最大分支的大小
vector < vector <int> > es;
void dfs(int u,int fa){//通过dfs求sz[],p[] 
    p[u]=fa;//初始化 
    sz[u]=1;//初始化 
    for(int i=0;i<es[u].size();i++){
        int v=es[u][i];     //找一个与之联通的点(子节点) 
        if(v==fa) continue; //排除掉v是父亲节点的情况 
        dfs(v,u);
        sz[u]+=sz[v];       //加上子节点的子树数量 
    }
} 
int main()
{
    cin>>n;
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        es[x].push_back(y);
        es[y].push_back(x);
    } 
    //输入
    dfs(1,0);
    //求得sz和p
    for(int u=1;u<=n;u++){
        for(int i=0;i<es[u].size();i++){
            int v=es[u][i];
            if(v==p[u]) continue; //排除父亲节点的可能
            f[u]=max(f[u],sz[v]); //计算u儿子为根的最大子树的的大小 
        }
    } 
    for(int u=1;u<=n;u++){
        g[u]=max(f[u],n-sz[u]);//g[u]由两部分的最大值取得:以u的儿子们形成的区块,u的长辈们组成的区块 
    }

    int id=min_element(g+1,g+1+n)-g;//找到最小的g 
    cout<<id<<" "<<g[id]<<endl; 
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。