Program experiment 2.a

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

思路

存储每个节点极其后续节点的度，因为对于该题，只依靠一个节点的度无法准确判断所有情况

Answer

具体思路见注释

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
using namespace std;

vector<int>G[7];//存储节点1-6的邻接点（G[0]用不到 ） 

int deg[7][7];/*deg[3][2]==1表示 在某个具有3个邻接点的结点所邻接的所有结点中 
                拥有2个邻接点的结点的数目为1 
              */ 
int main()
{
	int n;
    cin>>n;
    while(n--){
    	for(int i=1;i<=6;i++)G[i].clear();
    	memset(deg,0,sizeof(deg));
    	for(int i=1;i<=5;i++){
    		int u,v;
    		scanf("%d%d",&u,&v);
    		//将输入的邻接点压入vector 
    		G[u].push_back(v);
    		G[v].push_back(u);
		}
		for(int i=1;i<=6;i++){
			for(auto &x:G[i])
			deg[G[i].size()][G[x].size()]++;//遍历得到degree 
		}
	}
   
	if(deg[4][1]==3)cout<<"2,2-dimethylbutane";
	else if(deg[3][3]==2)cout<<"2,3-dimethylbutane";
	else if(deg[3][2]==2)cout<<"3-methylpentane";
	else if(deg[3][2]==1)cout<<"2-methylpentane";
	else cout<<"n-hexane";
	return 0;
}