题解 | 图的分类

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int>adj[n+1];//相连节点
    vector<int>degree(n+1,0);//度数组
    vector<bool>flag(n+1,1);//标记是否被访问过
    int num_2=0;//度大于2的节点的个数
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        degree[u]++;
        degree[v]++;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    queue<int> t;
    int counts=0;
    t.push(1);
    flag[1] = false;
    counts++;
    while(!t.empty()){
        int c = t.front();
        t.pop();
        int l = adj[c].size();
        for(int i=0;i<l;i++){
            if(flag[adj[c][i]]){
                flag[adj[c][i]] = false;
                t.push(adj[c][i]);
                counts++;
            }
        }
    }
    if(counts!=n){
        cout<<"unknown";//连通的节点数不等于总结点数
        return 0;
    }
    if(n==m){
        cout<<"ring";//边的数量等于结点数
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(degree[i]>2){
            num_2++;//找度大于2的节点个数
        }
    }
    if(num_2 ==0 && m == n-1){
        cout<<"line";//没有度大于2的节点，边数等于结点数-1
    }else if(num_2 ==1 && m == n-1){
        cout<<"star";//度大于2的节点只有一个（只有一个中心），其他的分支均为链状
    }else{
        cout<<"unknown";
    }

}