题解 | 图的分类

#include <iostream> 
#include <vector>
#include <cstring>

using namespace std;

int main () {
	int n, m;
	int degree[100005];
	memset(degree, 0, sizeof(degree));
	cin >> n >> m;
	int v1, v2, max_degree = -1;
	int i = m;
	while (i--) {
		cin >> v1 >> v2;
		degree[v1]++;
		degree[v2]++;
	}
	//统计degree = 1, degree = 2, degree > 2的点的个数 
	string ans = "unknown";
	int d_1 = 0, d_2 = 0, d_gt3 = 0, d_max = -1; 
	for (int i = 1; i < n + 1; i++) {
		if (degree[i] == 1) d_1++;
		else if (degree[i] == 2) d_2++;
		else {
			d_gt3++;
			d_max = max(d_max, degree[i]);
		}
	}
	if (m == n && d_2 == n) ans = "ring";
	else if (m == n - 1 && d_2 == n - 2 && d_1 == 2) ans = "line";
	else if (m == n - 1 && d_gt3 == 1 && d_1 == d_max) ans = "star";
	cout << ans << endl;
}