搬

搬

---

思路

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

• 链式图：$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;
}