学步园

       此题并查集加字典树，普通存储字符串会导致TLE。题目大意：你来调查每个人网络社交的规模，每给你两个人的名字，代表这两个人刚刚通过网络社交成为好友，就请你算出他们刚刚成为好友的新朋友圈有多少人。（根据朋友的朋友就是我的朋友这个规则，并且最开始每个人的朋友圈人数都为1（包括自己））

       我的解题思路：因为涉及到大量字符串，因此名字使用字典树来存储，使用并查集来算新朋友圈的人数。因为名字并没有事先有编号，所以我们要自己把这些名字一个个编号，这样再使用并查集就方便多了，另外再开一个存储当前节点为根节点时的集合元素个数的数组，这样每次合并操作后把元素个数也合并然后再输出答案就行了。

       注意：如果给出的两个人名已经是朋友关系的话，我们无须合并，直接输出这个朋友圈的人数就可以了。

       下面是我的解题代码：并查集加动态字典树

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

#define N 100009
#define M 22

struct dt       //定义字典树结构体
{
    dt *chid[52];
    int id;         //当前字符串为人名的编号
    dt()
    {
        memset(chid, 0, sizeof(chid));
        id = -1;
    }
};

int bleg[N];        //存储根节点
int rela[N];        //存储当前节点为根节点时的集合元素个数
char a[M], b[M];
int t, n;
int pn;             //所有已知人名的总数
dt *root;

void Init();        //初始化

int Find(int x);    //查找根节点

void Union(int x, int y);   //合并集合

void Delete(dt *p);     //删除字典树

int Insert(char str[]);     //将当前人名插入字典树，返回该人名的编号

int GetID(char ch);     //获得当前字符的对应下标

int main()
{
    while (~scanf("%d", &t))	//这个地方有点坑，如果写成scanf("%d", &t);就会WA
    {
        while (t--)
        {
            Init();
            scanf("%d", &n);
            while (n--)
            {
                scanf("%s %s", a, b);
                Union(Insert(a), Insert(b));
            }
        }
    }
    return 0;
}

void Init()
{
    int i;
    for (i=0; i<N; ++i) rela[i] = 1;
    pn = 0;
    Delete(root);
    root = new dt;
    return;
}

int Find(int x)
{
    int z, y = bleg[x];
    while (y != bleg[y])
    {
        y = bleg[y];
    }
    while (x != bleg[x])
    {
        z = bleg[x];
        bleg[x] = y;
        x = z;
    }
    return y;
}

void Union(int x, int y)
{
    int fx = Find(x);
    int fy = Find(y);
    if (fx == fy)       //已经是同一个朋友圈，不需要合并了
    {
        printf("%d\n", rela[fx]);
        return;
    }
    bleg[fx] = fy;
    rela[fy] += rela[fx];
    printf("%d\n", rela[fy]);
    return;
}

int Insert(char str[])
{
    int i;
    int strn = strlen(str);
    int chnum;
    dt *next = root;
    for (i=0; i<strn; ++i)
    {
        chnum = GetID(str[i]);
        if (next->chid[chnum] == NULL)
        {
            next->chid[chnum] = new dt;
        }
        next = next->chid[chnum];
    }
    if (next->id != -1) return next->id;    //已经存储过该人名，直接返回编号
    next->id = pn++;
    bleg[next->id] = next->id;
    return next->id;
}

void Delete(dt *p)
{
    int i;
    if (p == NULL) return;
    for (i=0; i<52; ++i)
    {
        if (p->chid[i] != NULL)
        {
            Delete(p->chid[i]);
        }
    }
    delete p;
    return;
}

int GetID(char ch)
{
    if (ch >= 'a' && ch <= 'z')
    {
        return ch - 'a';
    }
    return ch - 'A' + 26;
}