题目分析

题意简述

给定一组 $k$ 棵树 $C = \{T_1, T_2, \cdots, T_k\}$，每棵树 $T_i$ 恰好有 $n$ 个节点。需要将这些树划分为同构类，使得同一同构类中的任意两棵树彼此同构。对于每个同构类，按升序输出这些同构树的编号，并且所有同构类按第一个编号的字典序升序输出。

输入

• 第一行输入两个整数 $k$ 和 $n$，分别表示树的数量和每棵树的节点数，其中 $k$ 最大可达 $150$，$n$ 最大可达 $100$。
• 接下来的 $k$ 行，每行包含 $2n - 2$ 个整数，代表每棵树的 $n - 1$ 条（有向）边。

输出

对于每个同构类，在一行中按升序输出这些同构树的编号，不同编号之间用 = 分隔，行末以 ; 结尾。假设有 $m$ 个同构类，则输出 $m$ 行，且这些行按第一个编号的字典序升序排列。

解题思路

构建树结构

对于每棵树，根据输入的边信息构建树的结构，找到树的根节点，然后递归构建子树。

计算树的特征

为每棵树计算以下特征：

• 子节点数量：每个节点的子节点数量。
• 树的大小：以该节点为根的子树的节点总数。
• 树的深度：以该节点为根的子树的最大深度。
• 哈希值：根据树的大小、深度和子节点数量计算哈希值，用于快速判断两棵树是否可能同构。

哈希表分组

使用哈希表将具有相同哈希值的树分组，减少判断同构的范围。

判断同构

对于哈希表中同一组的树，通过递归比较节点的特征和子树的同构性，判断它们是否真正同构。

输出结果

遍历所有树，将同构的树划分为一组并输出。

代码实现

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

const int HASH = 2333;

int k,n;
struct tree{
    int size;
    int sucNo;
    vector<tree*> sucs;
    int depth;
    int hashVal;
    void getSucNo(){
        sucNo = sucs.size();
        for(int i = 0; i < sucNo; i++){
            sucs[i]->getSucNo();
        }
    }
    void getSize(){
        size = 0;
        for(int i = 0; i < sucNo; i++){
            sucs[i]->getSize();
            size += sucs[i]->size;
        }
        size += 1;
    }
    void getDepth(){
        if(!sucNo) {
            depth = 0;
            return;
        }
        depth = 0;
        for(int i = 0; i < sucNo; i++){
            sucs[i]->getDepth();
            if(depth < sucs[i]->depth) depth = sucs[i]->depth;
        }
        depth++;
    }
    void getHashVal(){
        hashVal = 0;
        for(int i = 0; i < sucNo; i++){
            sucs[i]->getHashVal();
            hashVal += sucs[i]->hashVal;
        }
        hashVal += size*size + depth*depth + sucNo*sucNo;
        hashVal %= HASH;
    }
}trees[200];

int idx[200];
int wz[200];
vector<int> hashtable[HASH];

void buildTree(int adjNo[110], int adjList[110][110], tree *tr, int rootIdx){
    if(!adjNo[rootIdx]) return;
    for(int i = 0; i < adjNo[rootIdx]; i++){
        tree *temp = new tree;
        tr->sucs.push_back(temp);
        buildTree(adjNo, adjList, temp, adjList[rootIdx][i]);
    }
}

bool isIsomph(tree *t1, tree *t2){
    if(t1->hashVal != t2->hashVal || t1->size != t2->size || t1->depth != t2->depth || t1->sucNo != t2->sucNo){
        return 0;
    }
    bool visited[150] = {0};
    for(int i = 0; i < t1->sucNo; i++){
        int offset = 0;
        for(; offset < t1->sucNo; offset++){
            if(!visited[offset] && isIsomph(t1->sucs[i], t2->sucs[offset])) {
                visited[offset] = 1;
                break;
            }
        }
        if(offset == t1->sucNo) return 0;
    }
    return 1;
}

int main() {
    scanf("%d%d", &k, &n);
    if(n == 1){
        for(int i = 1; i <= k; i++){
            printf("%d ", i);
            if(i != k) printf("= ");
        }
        printf(";\n");
        return 0;
    }
    for(int i = 1; i <= k; i++){
        int adjNo[110] = {0};
        int adjList[110][110];
        bool bei[110] = {0};
        for(int j = 0; j < n-1; j++){
            int a, b;
            scanf("%d%d", &a, &b);
            adjList[a][adjNo[a]] = b;
            adjNo[a]++;
            bei[b] = 1;
        }
        int root = 1;
        for(; root <= n && bei[root]; root++);
        //cout << root << endl;
        buildTree(adjNo, adjList, &trees[i], root);
        trees[i].getSucNo();
        trees[i].getSize();
        trees[i].getDepth();
        trees[i].getHashVal();
        idx[i] = trees[i].hashVal;
        wz[i] = hashtable[idx[i]].size();
        hashtable[idx[i]].push_back(i);
    }
    bool visited[200] = {0};
    for(int i = 1; i <= k; i++){
        if(visited[i]) continue;
        printf("%d ", i);
        visited[i] = 1;
        int sz = hashtable[idx[i]].size();
        for(int j = wz[i]+1; j < sz; j++){
            int d = hashtable[idx[i]][j];
            if(visited[d]) continue;
            if(isIsomph(&trees[i], &trees[d])){
                visited[d] = 1;
                printf("= %d ", d);
            }
        }
        printf(";\n");
    }
    return 0;
}

代码说明

1. 全局变量：
   • HASH：哈希表的大小，固定为 $2333$。
   • k 和 n：分别表示树的数量和每棵树的节点数。
   • trees[200]：存储所有树的数组。
   • idx[200]：存储每棵树的哈希值。
   • wz[200]：存储每棵树在哈希表中的位置。
   • hashtable[HASH]：哈希表，用于分组具有相同哈希值的树。
2. 树结构体：
   • tree 结构体包含树的各种信息，如大小、子节点数量、子节点指针、深度和哈希值。
   • getSucNo()：递归计算每个节点的子节点数量。
   • getSize()：递归计算以该节点为根的子树的节点总数。
   • getDepth()：递归计算以该节点为根的子树的最大深度。
   • getHashVal()：根据树的大小、深度和子节点数量计算哈希值。
3. 构建树函数：
   • buildTree()：根据邻接表信息递归构建树的结构。
4. 判断同构函数：
   • isIsomph()：判断两棵树是否同构，先比较哈希值、大小、深度和子节点数量，再递归比较子树。
5. 主函数流程：
   • 读取 $k$ 和 $n$，如果 $n = 1$，直接输出所有树编号。
   • 对于每棵树：
     • 读取边信息，构建邻接表。
     • 找到树的根节点。
     • 调用 buildTree() 构建树的结构。
     • 计算树的特征和哈希值。
     • 将树添加到哈希表中。
   • 遍历所有树，对于未访问的树，输出其编号，并在哈希表中查找同构的树，输出同构树的编号。