题解 | 图的分类

用vector直接统计节点所连边的条数解决(4ms)

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

int main() {
    cin.tie(0);ios::sync_with_stdio(0);//加速
    int a,b;
    cin>>a>>b;
    vector<int> cc(a+1);//统计每个节点的边数
    while(b--){
        int aa,bb;
        cin>>aa>>bb;
        cc[aa]++;cc[bb]++;
    }
    int cnt0=0,cnt1=0,cnt2=0;//分别统计有1 2 >2条边的节点个数
    for(int i=1;i<=a;i++){
        if(cc[i]==1){
            cnt0++;
        }else if(cc[i]==2){
            cnt1++;
        }else if(cc[i]==0){
            cout<<"unknown";return 0; //如果有零条边的点存在 直接unknown
        }else{
            cnt2++;
        }
    }
    if(cnt2>1){
        cout<<"unknown";
    }else if(cnt1==a){
        cout<<"ring";
    }else if(cnt0==2 && (cnt0+cnt1)==a){
        cout<<"line";
    }else {
        cout<<"star";
    }
}

用数组代替vector之后用delete[]释放内存 ，用scanf和printf代替cin和cout进行提速(3ms)

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

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    int* cc = new int[a + 1]();
    for (int i = 0; i < b; ++i) {
        int aa, bb;
        scanf("%d%d", &aa, &bb);
        cc[aa]++;
        cc[bb]++;
    }
    
    int cnt0 = 0, cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= a; ++i) {
        int c = cc[i];
        if (c == 0) {
            printf("unknown");
            delete[] cc;
            return 0;
        } else if (c == 2) { 
            cnt1++;
        } else if (c == 1) { 
            cnt0++;
        } else {
            cnt2++;
        }
    }
    
    if (cnt2 > 1) {
        printf("unknown");
    } else if (cnt1 == a) { 
        printf("ring");
    } else if (cnt0 == 2 && cnt2 == 0) { 
        printf("line");
    } else { 
        printf("star");
    }
    delete[] cc;
    return 0;
}