程序设计思维 A - 化学

题目

假设如上图，这个烷烃基有6个原子和5个化学键，6个原子分别标号1~6，然后用一对数字 a, b 表示原子a和原子b间有一个化学键。这样通过5行a, b可以描述一个烷烃基。
你的任务是甄别烷烃基的类别。

原子没有编号方法，比如
1 2
2 3
3 4
4 5
5 6
和
1 3
2 3
2 4
4 5
5 6
是同一种，本质上就是一条链，编号其实是没有关系的，可以在纸上画画就懂了。

Input
输入第一行为数据的组数T（1≤T≤200000）。每组数据有5行，每行是两个整数a, b(1≤a, b≤6, a ≤b)
数据保证，输入的烷烃基是以上5种之一

Output
每组数据，输出一行，代表烷烃基的英文名

Example
Input
2
1 2
2 3
3 4
4 5
5 6
1 4
2 3
3 4
4 5
5 6

Output
n - hexane
3 - methylpentane

思路

易知，每种化合物中都只含有5个化学键（即5条边）。
输入5条边后，统计6个原子的度。原子的度有4种：1、2、3、4。统计题目中5种化合物的不同度的原子的个数，可以得到如下的表：

例如，n-hexane化合物中，度为1的原子有2个、度为2的原子有3个、度为3的原子有0个、度为4的原子有0个（记作序列：2 3 0 0）。
可以发现，只有2-methylpentane和3-methylpentane两种化合物的原子的度序列完全相同，其他化合物的均不相同。因此，可以直接通过原子的度序列来区分n-hexane、2,3-dimethylbutane、2,2-dimethylbutane这三种化合物。当序列为3 2 1 0时，还需进一步进行判断。
对于2-methylpentane、3-methylpentane这两种化合物，如果以度为3的原子为根，可以发现2-methylpentane是一棵高度为4的树、3-methylpentane是一棵高度为3的树。

故可以根据判断树的高度来区分这两种化合物，笔者用的是层序遍历来计算树的高度。
至此，可以判断出所有的5种化合物。

代码

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
#include <stdlib.h>
#include <string.h>

using namespace std;


int T;
int a, b;

int area[7][7];
bool visit[7];

void printVector(vector<pair<int, int>>& v) {

	for (vector<pair<int, int>>::iterator it = v.begin(); it != v.end(); it++) {
		cout << (*it).first << " " << (*it).second << endl;
	}
	cout << endl;
}

int depth(int* cnt) {
	int s;	// 起点
	for (int i = 1; i < 7; i++) {
		if (cnt[i] == 3) {
			s = i;
			break;
		}
	}
	queue<int> q;
	map<int, int> mp; // <int x, int f> 表示第x个点在第f层

	q.push(s); visit[s] = 1; mp.insert({ s,1 });

	int max_dep = 1;

	while (!q.empty()) {
		int v = q.front();
		q.pop();
		int v_dep = (*(mp.find(v))).second;

		for (int i = 1; i < 7; i++) {
			if (area[v][i] == 1 && visit[i] == 0) {	//判断是否可达，且没被访问过
				q.push(i); visit[i] = 1; mp.insert({ i, v_dep + 1 });
				if (max_dep < v_dep + 1) max_dep = v_dep + 1;
			}
		}
	}

	return max_dep;
}

int main()
{
	cin >> T;
	for (int i = 0; i < T; i++) {
		vector<pair<int, int>> edge;
		//map<int, int> cnt;
		int cnt[7];	// 有6个原子，cnt[0]不使用
		memset(cnt, 0, sizeof(cnt));
		memset(area, 0, sizeof(area));
		memset(visit, 0, sizeof(visit));
		// 输入边
		for (int j = 0; j < 5; j++) {
			cin >> a >> b;
			edge.push_back({ a,b });
			area[a][b] = 1;
			area[b][a] = 1;
		}
		// 统计每个原子的度
		for (vector<pair<int, int>>::iterator it = edge.begin(); it != edge.end(); it++) {
			cnt[(*it).first]++;
			cnt[(*it).second]++;
		}

		/*for (int i = 0; i < 7; i++) {
			cout << i << ":" << cnt[i] << endl;
		}*/

		// 利用vector统计
		vector<int> cntV;
		for (int i = 1; i < 7; i++) cntV.push_back(cnt[i]);

		int d1 = count(cntV.begin(), cntV.end(), 1),
			d2 = count(cntV.begin(), cntV.end(), 2),
			d3 = count(cntV.begin(), cntV.end(), 3),
			d4 = count(cntV.begin(), cntV.end(), 4);

		//cout << d1 << " " << d2 << " " << d3 << " " << d4 << endl;

		/*for (int i = 1; i < 7; i++) {
			for (int j = 1; j < 7; j++) {
				cout << area[i][j] << " ";
			}
			cout << endl;
		}*/

		if (d1 == 2 && d2 == 4) cout << "n-hexane" << endl;
		else if (d1 == 4 && d3 == 2) cout << "2,3-dimethylbutane" << endl;
		else if (d1 == 4 && d2 == 1 && d4 == 1) cout << "2,2-dimethylbutane" << endl;
		else {	// 宽搜判断深度
			int dep = depth(cnt);
			//cout << dep << endl;
			if (dep == 4)cout << "2-methylpentane" << endl;
			else cout << "3-methylpentane" << endl;
		}

	}
}

完