题解：SP17819 XYI - XYI

cy950469 · 2026-10-21 15:48:09 · 题解

本题要求我们判断一棵树是怎样的类型（有 X,Y,Z 三种）。我们自然不可能让计算机建出树后直接判断，所以我们要充分利用人类智慧去找规律。

观察每个结点的度数，可以看到 X,Y 存在一个中心节点，其度数应分别为 4 和 3。而 I 不存在中心点，所有节点构成一条链。再看树的叶子节点，其度数为 1，X 有 4 个叶子节点，Y 有 3 个，I 有 2 个。除中心节点和叶子节点外的节点，其度数都应是 2。

于是可以先求每个结点的度数，然后统计各个度数的节点个数，最后根据度数判断类型即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;
inline void solve()
{
    int degree[505]={0};
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        degree[u]++;
        degree[v]++; //记录节点度数
    }
    int p[125001]={0};
    for(int i=1;i<=n;i++) p[degree[i]]++; //记录度数的节点数
    if(p[4]==1&&p[3]==0&&p[2]==n-5&&p[1]==4) puts("X"); //X
    else if(p[4]==0&&p[3]==1&&p[2]==n-4&&p[1]==3) puts("Y"); //Y
    else if(p[4]==0&&p[3]==0&&p[2]==n-2&&p[1]==2) puts("I"); //I
    else puts("NotValid"); //记得判无解
}
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cout<<"Case "<<i<<": ";
        solve();
    }
    return 0;
}