P10521 [XJTUPC2024] 瑟莉姆的宴会

liaoxingrui · 2024-05-21 16:50:40 · 题解

Content

有两个数 n 和 m。接下来还有 m 行，每行有 2 个数 x 和 y，表示 x 支配 y，同时支配具有传递性。

问编号为 i 的访客的直接支配者编号，总支配者的直接支配者编号为 0。

Solution

可以用并查集来做，判断两个客人是否是被同一个客人支配，如果不是，那么 x 就是 y 的直接支配者，最后将答案输出即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,x,y;
int f[N],ans[N];
inline int find(int x){
    if(f[x]==x)
        return x;
    return f[x]=find(f[x]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        int xx=find(x),yy=find(y);
        if(xx!=yy){
            f[yy]=xx;
            ans[y]=x;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}