题解 | 图的分类

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int degree[N];
map<int,int> mp;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,m;
	
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		degree[u]++;
		degree[v]++;
	}
	
	for(int i=1;i<=n;i++){
		mp[degree[i]]++;
	}
	
	if(mp[0]!=0){
		cout<<"unknown"<<endl;
	}else if(mp[2]==n-2&&mp[1]==2){
		cout<<"line"<<endl;
	}else if(mp[2]==n){
		cout<<"ring"<<endl;
	}else if(mp[n-mp[2]-1]==1&&mp[1]==n-mp[2]-1){
		cout<<"star"<<endl;
	}else{
		cout<<"unknown"<<endl;
	}
	
    return 0;
}