并查集 get ！

A4paper · 2018-10-10 14:40:11 · 个人记录

填坑：

传送门

说起并查集，上次做题还是好久之前的事情了。。。

这次，填一下之前的坑。

自然， num[t2] 也要加上 num[t1]，由于原先的第 t1 列没有了，所以 num[t1] = 0

对于 find 操作，注意在回溯的时候将 len[prn[x]] 赋给儿子，

注意，fa 是代表元素，不能用来更新 len[x]

int prn[MAXN];
int num[MAXN],len[MAXN]; //与队首的距离

int find(int x)
{
    if(prn[x] == x) return x;
    int fa = find(prn[x]);
    len[x] += len[prn[x]];
    return prn[x] = fa;
}

void Union(int x ,int y) //把 x 接在 y 后面
{
    int t1 = find(x);
    int t2 = find(y);
    len[t1] = num[t2];
    num[t2] += num[t1];
    num[t1] = 0;
    prn[t1] = t2;
}

int main(void)
{
    cin >> T;
    for(int i=1;i<=MAXN;i++)
    {
        prn[i] = i;
        num[i] = 1;
        len[i] = 0;
    }
    while(T--)
    {
        char c;
        int x,y;
        cin >> c >> x >> y;
        if(c == 'M')    Union(x,y);
        else
        {
            if(find(x) != find(y)) cout << "-1" << endl;
            else cout << abs(len[x]-len[y])-1 << endl;
        }
    }
    return 0;
}

男题：

传送门

与上一题都是用了带权并查集，

首先，要知道一个神奇操作叫逆序连边，因为这道题正向不好做（需要每次判断连通性），所以按时间顺序逆向连边，把时间作为边权，这样，最小的边权就是这一坨猴猴最早掉落的时间。

不过，在最后时刻，整张图并不是空的，而是会有一些猴子挂在树上，所以要提前把它们丢入并查集，并且掉落时间为无穷大（很合理，不是吗）

变量略多，会在代码中解释

int n,m;
int prn[MAXN];
int ans[MAXN];//存边（点？）权
int monkey[MAXN][2];//第 i 猴子的左（0）右（1）手连了哪只猴子
int vis[MAXN][2];//记录最后还连在树上的猴子和哪只手没有连猴（-1）

struct node{
    int num,dic;
}map[MAXN];//在第 i 时刻，第 num 只猴子的 dic 手松开了（左0右1）

int find(int x)
{
    if(x == prn[x]) return x;
    int fa = find(prn[x]);
    ans[x] = min(ans[x],ans[prn[x]]);//带权并查集中权值更新，详见上题
    return prn[x] = fa;
}

void Union(int x, int y, int z)
{
    int t1 = find(x);
    int t2 = find(y);
    if(t1 == t2) return;
    if(t1 == 1)
    {
        prn[t2] = t1;
        ans[t2] = z;
    }
    else
    {
        prn[t1] = t2;
        ans[t1] = z;
    }
}

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) prn[i] = i;
    for(int i=1;i<=n;i++)
    {
        cin >> monkey[i][0] >> monkey[i][1];
        if(monkey[i][0] == -1) vis[i][0] = 1;
        if(monkey[i][1] == -1) vis[i][1] = 1;
        //猴子手上不再连有猴子时，记下来
    }
    for(int i=1;i<=m;i++)
    {
        int u,d;
        cin >> u >> d;
        map[i].num = u;
        map[i].dic = d-1;
        vis[u][d-1] = 1;
        //这只猴子松开了手，记下来
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i][0])  Union(i,monkey[i][0],m);
        if(!vis[i][1])  Union(i,monkey[i][1],m);
        //如果这只猴子没有松过手，并且有猴子在它手上，丢进去
    }
    memset(ans,0x3f,sizeof ans);
    for(int i=m;i>0;i--)
        Union(map[i].num,monkey[map[i].num][map[i].dic],i-1);
    for(int i=1;i<=n;i++)
    {
        find(i);
        if(ans[i] == 0x3f3f3f3f) cout << "-1" << endl;
        else cout << ans[i] << endl;
    }
    return 0;
}