首页 > 其他分享 >题解:CF771A Bear and Friendship Condition

题解:CF771A Bear and Friendship Condition

时间:2024-08-02 12:17:27浏览次数:13  
标签:联通 int 题解 long fa Friendship find Condition

CF771A Bear and Friendship Condition 题解

算法

并查集,图的基本性质

分析

题目意思是,一旦有一些点联通,那么这些点必须两两直接相连。换句话讲,就是图中的每个联通块都是完全图

所谓完全图,就是图中的每个点都两两相连,假设一个完全图有 \(n\) 个点,那么我们可以通过乘法原理算出这个完全图的边数为 \(\frac{n\times(n-1)}{2}\)。那么我们现在只需要用并查集统计一下联通块个数,顺便统计一下每个联通块的点数,算出来所有完全图的边数之和与 \(m\) 比较即可。

注意要开 long long

示例代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace Ryan
{
    const int N=150005;
    int n,m;
    int fa[N],sum[N],vis[N];
    int find(int x)
    {
        return (x==fa[x]?x:fa[x]=find(fa[x]));
    }
    void merge(int x,int y)
    {
        int ff=find(x);
        int fy=find(y);
        fa[ff]=fy;
        sum[fy]+=sum[ff];
        return;
    }
    signed work()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            fa[i]=i,sum[i]=1;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            cin>>x>>y;
            if(find(x)!=find(y))
                merge(x,y);
        }
        int k=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            int x=find(i);
            if(vis[x])continue;
            vis[x]=1;
            k+=sum[x]*(sum[x]-1)/2;
            ans++;
        }
        if(k==m)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        return 0;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return Ryan::work();
}

标签:联通,int,题解,long,fa,Friendship,find,Condition
From: https://www.cnblogs.com/RyanAdam/p/18338488

相关文章

  • 题解:CF507C Guess Your Way Out!
    CF507CGuessYourWayOut!题解算法模拟思路按照左右左右的方式先往下找,每次找到一个子节点时就看此节点为根的子树是否包含目标节点,如果包含就继续往下走,不包含说明目标叶子节点在另一边的子树上,那么肯定是先需要把这边的子树遍历完才能换到另一边,所以答案直接加上这个子树......
  • HT-018 Div3 构造 题解 [ 黄 ] [ 数学 ] [ 结论 ]
    构造:结论题,gcy数竞大佬tql%%%orz。结论先放结论:如果\(x\bmod4=2\),那么\(x\)无法被表示为\(a^2-b^2\)的形式;除此之外的其他数都可以。证明对\(a^2-b^2\)因式分解,得\(x=(a+b)(a-b)\)。当\(x\bmod2=1\)时包含\(x\bmod4=1\)和\(x\bmod4=3\)的情况。......
  • Educational Codeforces Round 168 (Rated for Div. 2)A——D题解
    EducationalCodeforcesRound168(RatedforDiv.2)A——D题解A.StrongPassword题意:给一个小写字符串密码,添加一个小写字母,使得密码更加复杂。题解:有相同的相邻的字母,再其中间添加不同的字母;如果没有相同的相邻的字母,则最后添加一个字母。#include<bits/stdc++.h>......
  • HT-018 Div3 能量消耗 题解 [ 绿 ] [ 线性 dp ] [ 前缀和优化 ]
    能量消耗:一个前缀和优化dp的大典题,要是数据水一点\(O(n^3)\)都能硬草过去。思路显然,定义\(dp[i]\)为考虑前\(i\)个塔,并且将前面的精灵全部收集的最小代价。于是转移:\[dp[i]=min(dp[i],dp[j]+w(j,i)+c[i])\]其中\(0\lej<i\lem\),\(w(j,i)\)表示收集从塔\(j\)到......
  • CF1987C Basil's Garden 题解
    CF1987CBasil'sGarden题解壹·题目描述有$n$个数字排成一排,接下来每隔一秒进行一次操作:如果$i=n$或$h_i>h_{i+1}$,则第$i$盆花的高度$h_i$将变为$\max(0,h_i-1)$。请问至少经过多少秒后,所有的数字都为$0$。贰·思路分析可以知道,$h_i\leq1$时$h_i←0$。显然可......
  • [题解]P6927 [ICPC2016 WF] Swap Space
    思路显然要按\(a_i,b_i\)的大小关系分类:\(a_i<b_i\):假令有两对数\((a_1,b_1),(a_2,b_2)\),且\(a_1\leqa_2\)。如果\(b_1\geqa_2\)。则按照12的顺序,将带来\(a_1\)的花费,以及\(b_1+b_2\)的额外空间;而按照21的顺序,将带来\(a_2\)的花费,以及\(b_1+b_2......
  • CF553E Kyoya and Train 题解
    Description给定一张\(n\)个点\(m\)条边的无重边无自环的有向图,你要从\(1\)号点到\(n\)号点去。如果你在\(t\)时刻之后到达\(n\)号点,你要交\(x\)元的罚款。每条边从\(a_i\)到\(b_i\),走过它需要花费\(c_i\)元,多次走过同一条边需要多次花费。走过每条边所需......
  • 【问题解决方案】npm install报错问题:npm ERR! - 多种解决方案,总有一种可以解决
    @[toc]1.问题重述安装package.json里面的包,使用npminstall但是报错2.解决方案方案1.确认根目录正确确认自己的目录是根目录(也就是处于./package.json可以找到的位置)例如--根目录----package.json----其他文件----其他文件方案2.确认文件名正确确认自己的pack......
  • P9308 「DTOI-5」#1f1e33 题解
    声明:截止\(2024.8.1\),拿下洛谷最优解最短解,代码长度不到1k。复杂度\(O(n\log\logn)\)。先骂:官方题解菜!这种纯洁的数论题居然敢引入NTT作为标算,说明出题人不会推式子。还有题解区一车\(\log\)的题解凭啥顶那么上面,推的一坨狗屎推出来的复杂度还不优秀。说明:下面除法默......
  • 2024牛客暑期多校训练营6 A.cake(题解)
    A.Cake题意两个人玩游戏,游戏分两阶段第一阶段在一棵有根树上轮流走,走到叶子停止,有根树边上有01标记,记录下走过的01串第二阶段分蛋糕,Oscar按自己的意愿切蛋糕,然后按照第一阶段获得的01串顺序依次拿蛋糕(1代表Grammy拿,0代表Oscar拿)两人都想让自己获得尽量多的蛋糕,......