烷烃基的类别

问题描述

化学很神奇，以下是烷烃基。

Name	HDMG	Name	HDMG
n-hexane		2-methylpentane
3-methylpentane		2,3-dimethylbutane
2,2-dimethylbutane		-	-

假设如上图，这个烷烃基有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

解题思路

1. 对烷烃基标号

   对于每一个标号可以用数组标号+1表示，其连接的其他碳原子标号-1用链表储存。
   对于上述5种烷烃基，可以得到如下邻接链表结构：

   | Name | HDMG | Structure |
   | ————————— | ——————————— | —————————————————————————————— |
   | n-hexane | | [1]→2
[2]→1→3
[3]→2→4
[4]→3→5
[5]→4→6
[6]→5 |
   | 2-methylpentane | | [1]→2
[2]→1→3→4
[3]→2
[4]→2→5
[5]→4→6
[6]→5 |
   | 3-methylpentane | | [1]→2
[2]→1→3
[3]→2→4→5
[4]→3
[5]→3→6
[6]→5 |
   | 2,3-dimethylbutane | | [1]→2
[2]→1→3→4
[3]→2
[4]→2→5→6
[5]→4
[6]→4 |
   | 2,2-dimethylbutane | | [1]→2
[2]→1→3→4→5
[3]→2
[4]→2
[5]→2→6
[6]→5 |

2. 初次鉴别
   标号不管怎么变都无法影响烷烃基的种类，但是观察邻接链表，不难发现链长可以进行初次区分。

   | 正己烷 | 2-甲基苯丙烷 | 3-甲基苯丙烷 | 2,3-二甲基丁烷 | 2,2-二甲基丁烷 |
   | :——: | :—————: | :—————: | :——————: | :——————: |
   | 1 | 1 | 1 | 1 | 1 |
   | 2 | 3 | 2 | 3 | 4 |
   | 2 | 1 | 3 | 1 | 1 |
   | 2 | 2 | 1 | 3 | 1 |
   | 2 | 2 | 2 | 1 | 2 |
   | 1 | 1 | 1 | 1 | 1 |

可以设3个int变量count2, count3, count4用来记录链长 = x的出现次数。
只有2,2-dimethylbutane的count4 = 1;
只有n-hexane的count2 = 4;
只有2,3-dimethylbutane的count3 = 2;
对于2-methylpentane和3-methylpentane，count2 = 2, count3 = 1, count4 = 0，无法通过链长来区分。

1. 鉴别2-methylpentane和3-methylpentane
   不难发现，不管怎么编号(正/反)，当链长 = 3时，与这个碳原子相连的甲基个数不同。因此可记录链长 = 3时数组编号no，然后找到此数组所在的链arr[no]，记录该条链储存的元素，即记录与之相连的碳原子的编号。
   比如图中2-methylpentane与2相连的是1, 3, 4，属于甲基(即链长 = 1)的是1, 3;
   3-methylpentane与3相连的是2, 4, 5，属于甲基的是4。
   2-methylpentane的甲基个数为2，3-methylpentane的甲基个数为1，以此鉴别。

数据结构及实现方法

采用邻接链表表示的有向图，本题只需提供插入、查找、遍历操作。详见源代码注释。

源代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

/*链表的节点*/
struct node {
	int a;
	node* next;
	node() { a = 0; next = NULL; }
	node(const int& a) { this->a = a; next = NULL; }
	node(const int& a, node* next) {
		this->a = a;	this->next = next;
	}
};

/*链表*/
class chain {
protected:
	node* firstNode;//指向链表头节点的指针
	int listSize;//链表长度
public:
	chain(int initialCapacity = 10) {//初始化构造函数
		firstNode = NULL;
		listSize = 0;
	}
	chain(const chain&);
	~chain() {//析构函数
		while (firstNode != NULL) {
			node* nextNode = firstNode->next;
			delete firstNode;
			firstNode = nextNode;
		}
	}
	int getSize() { return listSize; }//返回链表长度
	void insert(const int& theElement) {//链表的有序插入操作
		if (firstNode == NULL)//当链表为空时，直接插入
			firstNode = new node(theElement, firstNode);
		else {//链表非空时
			node* p = firstNode;//指向头节点的指针
			node* pp = NULL;//指针pp紧跟p的后面
			while (p != NULL && p->a < theElement) {//要插入的元素小于当前指向的节点
				pp = p;//pp跟上p
				p = p->next;//p指向下一节点
			}
            //到了合适的插入位
			node* newNode = new node(theElement, p);//新建节点，插入的元素指向p
			if (pp == NULL)//当插入为头节点时
				firstNode = newNode;
			else//否则，插入点之前的指针指向新节点
				pp->next = newNode;
		}
		listSize++;//每次成功插入，链表大小+1
	}
	int indexOf(const int& theElement) const {//获取该元素所在位置
		node* currentNode = firstNode;
		int index = 0;
		while (currentNode != NULL && currentNode->a != theElement) {//遍历即可
			currentNode = currentNode->next;
			index++;
		}
		if (currentNode == NULL)
			return -1;//未找到时返回-1
		else
			return index;//找到时返回index
	}
	vector<int> getElement() {//遍历，获取链表所有元素，用vector储存
		vector<int> nei;
		node *p = firstNode;
		while (p != NULL) {
			nei.push_back(p->a);
			p = p->next;
		}
		return nei;
	}
};

class ane {//烷烃基无向图的类
private:
	chain arr[6];//邻接链表，每个碳原子标号，0~5一一对应
	int chainSize[6];//记录每条链的大小
public:
	ane(){ }
	~ane(){ }
	void insert(int a, int b) {//向无向图中插入点
		if (arr[a].indexOf(b) == -1) {//未找到，即标号还未存在时插入
			arr[a].insert(b);
		}
	}
	void getSize() {//6个点插入完成后，记录每条链大小
		for (int i = 0; i < 6; i++) {
			chainSize[i] = arr[i].getSize();
			//cout << chainSize[i] << endl;
		}
	}
	string type() {//判断属于哪种烷
		int count2 = 0, count3 = 0, count4 = 0;/*分别记录
		链长 = 2，链长 = 3，链长 = 4出现次数*/
		for (int i = 0; i < 6; i++) {
			if (chainSize[i] == 2)
				count2++;
			if (chainSize[i] == 3)
				count3++;
			if (chainSize[i] == 4)
				count4++;
		}
		if (count2 == 4)
			return "n-hexane";//链长 = 2 出现4次
		if (count4 == 1)
			return "2,2-dimethylbutane";//链长 = 4 出现1次
		if (count3 == 2)
			return "2,3-dimethylbutane";//链长 = 3 出现2次
        //以上区分出3种，剩下2种另外区分
		else if (count2 == 2 && count3 == 1 && count4 == 0) {
			int no = 0;// no用于记录 链长 = 3 所在数组位置
			for (int i = 0; i < 6; i++)
				if (chainSize[i] == 3)
					no = i;//找到位置i
			vector<int> nei = arr[no].getElement();//获得该链元素
			int count1 = 0;//记录甲基个数
			for (int i = 0; i != nei.size(); i++)
				if (chainSize[nei.at(i)] == 1)
					count1++;
			if (count1 == 2)
				return "2-methylpentane";//甲基个数 = 2 得出
			else
				return "3-methylpentane";//否则，甲基个数 = 1
		}

	}
};

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		ane tane;
		for (int j = 0; j < 5; j++) {
			int a, b;
			cin >> a >> b;
			tane.insert(a - 1, b - 1);
			tane.insert(b - 1, a - 1);
		}
		tane.getSize();
		cout << tane.type() << endl;
	}

	return 0;
}