题解：CF292B Network Topology

leo120306 · 2024-06-25 16:34:54 · 题解

思路

首先读题。题目让我们判断给定的图是链式图，环形图还是菊花图。搞清楚定义就很简单了：

• 链式图：2 个点度数为 1，其余图度数为 2。
• 环形图：所有点度数为 2 且连通。
• 菊花图：一个点度数为 n-1，其余点度数为 1。

可以发现判定度数的条件只需要记录每个点的度数并计数，无需构图。那么对于环形图，连通性怎么判断？难道要用并查集吗？其实不然。认真扫视一遍英文题面，我们注意到这样一句话：

It's known that any two computers connected by cable directly or through other computers.

这句话就告诉你这张图一定连通，所以连通性就不用判了。中文题面居然没写上，太坑了。 知道了这些，我们就可以直接开始敲代码了：记录度数，各度数计数，判断输出。

实现

还是比较简单的。

#include <cstdio>
using namespace std;

namespace io{ // 快读快写已省略
    inline int readi(){
        int i;
        scanf("%d",&i);
        return i;
    }
    #define writes puts
};
using namespace io;

int n,m,d[100005];

int main(){
    int n=readi(),m=readi();
    for(int i=1;i<=m;i++){
        int x=readi(),y=readi();
        d[x]++,d[y]++;
    }
    int cnt1=0,cnt2=0,cnt3=0;
    for(int i=1;i<=n;i++){
        d[i]==1&&cnt1++;
        d[i]==2&&cnt2++;
        d[i]==n-1&&cnt3++;
    }
    if(cnt1==2&&cnt2==n-2)writes("bus topology");
    else if(cnt2==n)writes("ring topology");
    else if(cnt3&&cnt1==n-1)writes("star topology");
    else writes("unknown topology");
//  flush();

    return 0;
}