求助,为什么我有几个点错了
查看原帖
求助,为什么我有几个点错了
556824
hhyyd楼主2022/3/8 15:31
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n;
vector<int> g[N];
int cnt[N]; //记录每个点的子节点数量
bool st[N];
int dfs(int idx)
{
    st[idx] = true;
    int sum = 1;
    for(int i=0;i<g[idx].size();i++)
    {
        int ver = g[idx][i];
        if(!st[ver])
        {
            sum+=dfs(ver);
        }
    }
    cnt[idx] = sum;
    return sum;
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1);
    vector<int> ans;
    //遍历每一个点,判断它作为根节点的时候是否可行
    for(int i=1;i<=n;i++)
    {
        if(g[i].size()==1)
        {
            //如果这个节点只连了一个节点,那它可以作为根节点
            ans.push_back(i);
        }
        else
        {
            int sum = 0;
            for(int j=0;j<g[i].size();j++)
            {
                int ver = g[i][j]; //如果它的某个子节点的数量大于它的子节点数量,说明,大的节点在遍历过程中是它的父节点
                if(cnt[ver] > cnt[i])
                {
                    sum^=(n-cnt[i]); //父节点所代表的那一部分树的节点数为n-cnt[i];
                }
                else
                {
                    sum^=cnt[ver];
                }
            }
            //如果所有的子节点都相等,那么它可以作为根
            if(sum == 0) ans.push_back(i);
        }
    }
    sort(ans.begin(),ans.end());
    for(auto x : ans)
    {
        cout<<x<<" ";
    }
    cout<<"\n";
    return 0;

}

2022/3/8 15:31
加载中...