这周的总结

这周主要学习了并查集的内容，学到了一些关于并查集的知识点及用法。

简单介绍一下并查集的用法：一共有两种，首先是合并，就是把一个根节点的所有子节点合并成一个集合，其次是查询，查询这个点属于哪个集合时，比较容易查询。简而言之，并查集就是可以高效的对元素进行分组并合并在一起，并且能快速的查询两个元素是否属于同一组。

知识点相当容易理解，但和题目结合在一起，就是有点困难了，平常是不会想到并查集这个解决方法的，但是学了就学会用这种方法去做，简单而又不难写。

关于并查集，也有优化方法，第一，就是按秩合并，就是合并时，不是那个并查集的结构类似于树状结构吗，合并时就看这两棵树的高度来看谁当父节点。第二个方法，就是路径压缩，将所有的子节点全部指向唯一的那个根节点，这样查询时就能更快的去查找了。

关于并查集的代码及其优化方法的代码就不用再写了，看一下我觉得比较典型的题目。

就是给出n个动物，k句话，在k句话中有真话和假话，话语中有两种操作，第一个是第几种和第几种是同类，另一个就是谁能吃谁，求其中假话的数量。

这是一个典型的运用并查集的例题，就是有天敌，同类，还有猎物。根据题意，x,y要么是同类要么是x吃y，x吃y，x是y的天敌，y是x的猎物，x的天敌是y的猎物。根据这个关系来写判断语句，而且根据这个确定数组的大小为3*n。

#include 
using namespace std;
int fa[150005];
int ans;
int find(int x)
{
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

inline void merge(int x, int y)
{
    fa[find(x)] = find(y);
}
inline bool same(int x, int y)
{
    return find(x) == find(y);
}

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= 3 * n; i++)
        fa[i] = i;
    for (int i = 1; i <= k; i++)
    {
        int c, x, y;
        cin >> c >> x >> y;
        if (x <= n && y <= n)
        {
            if (c == 1)
            {
                if (!same(x, y + n) && !same(x, y + 2 * n))
                {
                    merge(x, y);
                    merge(x + n, y + n);
                    merge(x + 2 * n, y + 2 * n);
                }
                else ans++;
            }
            else
            {
                if (x != y)
                {
                    if (!same(x, y) && !same(x, y + n))
                    {
                        merge(x + n, y);
                        merge(x + 2 * n, y + n);
                        merge(x, y + 2 * n);
                    }
                    else ans++;
                }
                else ans++;
            }
        }
        else ans++;
    }
    cout << ans << endl;
    return 0;
}

这个题非常典型，合并查找，用并查集做这个题真的非常方便。

就是有n个人，其中0是最初感染者，写出m个组，在一个组中都会被感染，求出最终感染的人数。

典型的并查集的题，和上面的题差不多，但比上面题略微简单一点，就是把同组的用所有成员并在一起，并查询与0同组的成员的数量。

#include 
using namespace std;
int fa[30005], sum[30005];
int find(int n)
{
	return fa[n] == n ? n : fa[n] = find(fa[n]);
}
void merge(int x, int y)
{
	int fx, fy;
	fx = find(x);
	fy = find(y);
	if (fx < fy)
	{
		fa[fy] = fx;
		sum[fx] += sum[fy];
	}
	if (fx > fy)
	{
		fa[fx] = fy;
		sum[fy] += sum[fx];
	}
}
int main()
{
	int n, m, k, a, b;
	while (cin >> n >> m)
	{
		for (int i = 0; i <= n; i++)
		{
			fa[i] = i;
			sum[i] = 1;
		}
		if (n == 0 && m == 0)break;
		for (int i = 0; i < m; i++)
		{
			cin >> k >> a;
			for (int j = 1; j < k; j++)
			{
				cin >> b;
				merge(a, b);
			}
		}
		cout << sum[0] << endl;
	}
	return 0;
}

这些题是比较典型的题，要经常回过头去看看，搜索的题又有点不怎么看得懂了，下周得回过头看看去，把下周的题目提前做完，去做搜索题去。都要加油！！！