题解 | 图的分类

//所有节点度数均为2是环形
//所有节点中有两个结点度为1，其它结点度为2是链型
//在上述两种情况之外，所有节点中只有度为1和2的结点以及一个度大于等于3的结点，是星型
#include <iostream>
#include <vector>
using namespace std;

int main() {
    //读入数据
    int n, m;
    cin >> n >> m;
    
    //记录计算机结点度的数组
    vector<int> du(n, 0);
    //获取每个节点的度
    for(int i = 0; i < m; i++){
        int x , y;
        cin >> x >> y;
        du.at(x - 1)++;
        du.at(y - 1)++;
    }
    
    //度为1、2和超过2的节点个数
    int du_1 = 0;
    int du_2 = 0;
    int du_over2 = 0;
    for(int i = 0; i < n; i++){
        if(du.at(i) == 1){
            du_1++;
        }
        else if(du.at(i) == 2){
            du_2++;
        }
        else if(du.at(i) > 2){
            du_over2++;
        }
        else{}
    }
    //判断并输出结果
    if(du_2 == n){
        cout << "ring" << endl;
    }
    else if(du_1 == 2 && du_2 == n - 2){
        cout << "line" << endl;
    }
    else if(du_over2 == 1 && du_1 + du_2 == n - 1){
        cout << "star" << endl;
    }
    else{
        cout << "unknown" << endl;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")