这节课讲并查集
数据结构一共讲7节课
1.并查集
2.树状数组
3.线段树
4.可持久化数据结构
5.平衡树——treap
6.AC自动机
int find(int x) // 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
p[x]是x的祖宗节点
路径压缩优化
时间复杂度可以看做O(logn)
并查集可以
1.合并两个集合
2.查询某一个元素的祖宗节点
扩展：
1.记录每一个集合的大小
可以绑定到根节点上
2.每个点到根节点的距离
可以绑定到每一个元素上
扩展2可以处理一个重要的问题，可以解决ACwing食物链那一道题目
食物链这一道题目也可以用拓展并查集来做
我们只维护相对关系
拓展并查集是一种枚举的思想
不过带权的并查集好一些
acwing 1250:：格子游戏

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n,m;
pair<int,int> p[N][N];
pair<int,int> find(int x,int y)
{
    if (p[x][y]!=make_pair(x,y)) p[x][y] = find(p[x][y].first,p[x][y].second);
    return p[x][y];
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            p[i][j]={i,j};
    for(int i=1;i<=m;i++)
    {
        int a,b;
        char t;
        cin>>a>>b>>t;
        if(t=='D')
        {
            auto t1=find(a,b),t2=find(a+1,b);
            if(p[t1.first][t1.second]==p[t2.first][t2.second])
            {
                cout<<i;
                return 0;
            }
            p[t1.first][t1.second]=p[t2.first][t2.second];
        }
        else
        {
            auto t1=find(a,b),t2=find(a,b+1);
            if(p[t1.first][t1.second]==p[t2.first][t2.second])
            {
                cout<<i;
                return 0;
            }
            p[t1.first][t1.second]=p[t2.first][t2.second];
        }
    }
    cout<<"draw";
    return 0;
}