acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 第二!

    userId_undefined
    哒烧叶
    31阅读
    1回复
    2点赞
  • 题解

    userId_undefined
    法兰西玫瑰
    33阅读
    0回复
    0点赞
  • 题解

    userId_undefined
    zsy
    题解仙人时空双修者快乐小狗BUG超度大师秩序白银
    4阅读
    0回复
    2点赞
  • 第三!

    userId_undefined
    fufu
    20阅读
    0回复
    0点赞
  • A567.亲戚1

    #include<bits/stdc++.h> using namespace std; const int maxn = 5e3 + 9; int fa[maxn]; int get(int x){//找到祖宗,不是的话向上递归 if (fa[x] == x) return x; return get(fa[x]); } void merge(int x,int y){//合并集合 fa[get(x)] = get(y); } int main(){ int n,m,p; cin >> n >> m >> p; for(int i = 1;i <= n;i ++) fa[i] = i; for(int i = 0;i < m;i ++){ int u,v; cin >> u >> v; if(get(u) != get(v)) merge(u,v);//如果不是同祖宗,合并 } while(p--) { int x,y; cin >> x >> y; if(get(x) == get(y)) cout << "Yes" << '\n';//判断是否是亲戚 else cout << "No" << "\n"; } return 0; }

    userId_undefined
    杭州必吃榜榜首-李洪宇
    空间掌握者倔强青铜出道萌新模拟·模拟练习生
    9阅读
    0回复
    0点赞
  • 题解

    userId_undefined
    Alxe
    6阅读
    0回复
    0点赞
  • 题解

    很简单的并查集模版。先把每个亲戚合并,之后判断是不是一个祖先就行。 这里是按秩合并+路径压缩优化,所以复杂度是 O(ma(n))O(ma(n))O(ma(n)) 。至于这个 𝛼(n)𝛼(n)𝛼(n) 是个啥你不用了解。反正对于 n≤210000010000114514n\leq2^{100000^{10000^{114514}}}n≤210000010000114514 总有 𝛼(n)≤5𝛼(n)\leq5𝛼(n)≤5

    userId_undefined
    ༺དༀ༒∞░∞༒ༀཌ༻(不加团)
    7月全勤卷王8月全勤卷王题解仙人GESP4级传道者BUG超度大师
    2阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页