牛客多校第十场 H Stammering Chemists 判断图同构

题意：

给出一个无向图，表示一种有机物质的结构式，问你这个有机物质是列表中的哪个。

题解：

判断图同构需要枚举全排列以对应点，但是此题中几乎只需要将点度数排序后一个一个比较，对于甲基位置再加个特判即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

typedef long long ll;

typedef pair<int, LL>P;

const int M = 1e2 + ;

const LL mod = 1e9 + ;

const LL lINF = 0x3f3f3f3f3f3f3f3f;

#define ls (rt<<1)

#define rs (rt<<1|1)

vector<int>ve[M];

vector<int>ve2;

int a[][] = { {,,,,,},{,,,,,},{,,,,,},{,,,,,} };

int flag;

bool isv[M];

int ans;

void dfs(int x, int step)

{

    isv[x] = ;

    ans = max(ans, step);

    for (int i = ; i < ve[x].size(); i++)

    {

        if (!isv[ve[x][i]])

        {

            dfs(ve[x][i], step + );

        }

    }

}

int main()

{

    int _;

    scanf("%d", &_);

    while (_--)

    {

        for (int i = ; i <= ; i++)

        {

            ve[i].clear();

        }

        for (int i = ; i <= ; i++)

        {

            int l, r;

            scanf("%d%d", &l, &r);

            ve[l].push_back(r);

            ve[r].push_back(l);

        }

        ve2.clear();

        for (int i = ; i <= ; i++)

        {

            ve2.push_back(ve[i].size());

        }

        sort(ve2.begin(), ve2.end());

        for (int i = ; i < ; i++)

        {

            flag = i;

            for (int j = ; j < ; j++)

            {

                if (ve2[j] != a[i][j])

                {

                    flag = ;

                    break;

                }

            }

            if (flag != )

                break;

        }

        if (flag == )

        {

            printf("n-hexane\n");

        }

        else if (flag == )

        {

            ans = ;

            memset(isv, , sizeof isv);

            for (int i = ; i <= ; i++)

            {

                if (ve[i].size() == )

                {

                    dfs(i, );

                }

            }

            if (ans == )

                printf("2-methylpentane\n");

            else

                printf("3-methylpentane\n");

        }

        else if (flag == )

        {

            printf("2,3-dimethylbutane\n");

        }

        else if (flag == )

        {

            printf("2,2-dimethylbutane\n");

        }

    }

}