首页 > 其他分享 >P1989 无向图三元环计数

P1989 无向图三元环计数

时间:2024-07-27 13:07:29浏览次数:14  
标签:遍历 int sqrt 100005 计数 无向 du 节点 P1989

原题链接

题解

暴力方法:

遍历每个节点,遍历每个节点的子节点,遍历每个子节点的子节点,看看子子节点是否是节点的子节点,时间复杂度 \(O(nm^2)\)

优化

考虑无向边建边的时候建成有向边,且两个点建边时,度数小的指向度数大的,如果度数相等,编号小的指向编号大的(其实这一步是为了避免重复计数)(启发式建边???)时间复杂度 \(O(m\sqrt{m})\)

证明:

每个节点,最多有 \(\sqrt{m}\) 条出边,如果原始无向图中,某个点有 \(k\) 条边

  • 如果 \(k<\sqrt{m}\) 那么其出边也不会超过 \(\sqrt{m}\)

  • 如果 \(k\geq \sqrt{m}\) 那么其只会指向边比它更多的点,这样的点不超过 \(\sqrt{m}\)

所以相当于遍历每个有向边,然后遍历终点的出边,查看是否也是起点的一条出边的终点(因为不存在有向三元环,这样也避免了重复计数)

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

vector<int> G[100005];
int out[100005]={0};
int vis[100005]={0};
int a[200005]={0};//edge
int b[200005]={0};
int du[100005]={0};

void solve()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i];

        du[a[i]]++;
        du[b[i]]++;
    }

    for(int i=1;i<=m;i++)
    {
        int x=a[i],y=b[i];
        if(du[x]>du[y]) G[y].push_back(x);
        else if(du[x]<du[y]) G[x].push_back(y);
        else if(x<y) G[x].push_back(y);
        else G[y].push_back(x);
    }

    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        for(auto it:G[i]) vis[it]=i;

        for(auto next:G[i])
        {
            for(auto nnext:G[next])
            {
                if(vis[nnext]==i) ans++;
            }
        }
    }

    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}


标签:遍历,int,sqrt,100005,计数,无向,du,节点,P1989
From: https://www.cnblogs.com/pure4knowledge/p/18326836

相关文章

  • 【MATLAB源码】机器视觉与图像识别技术(4)---模式识别与视觉计数
    系列文章目录第一篇文章:【MATLAB源码】机器视觉与图像识别技术—视觉系统的构成(视频与图像格式转换代码及软件下载)第二篇文章:【MATLAB源码】机器视觉与图像识别技术(2)—图像分割基础第三篇文章:【MATLAB源码】机器视觉与图像识别技术(2)续—图像分割算法第四篇文章:【MATL......
  • 按小计和计数对 Pandas 数据框进行排序
    我有一个非常大的数据集,名为bin_df。使用pandas和以下代码,我为每个组分配了小计“总计”:bin_df=df[df["category"].isin(model.BINARY_CATEGORY_VALUES)]bin_category_mime_type_count_df=(bin_df.groupby(["category","mime_type&quo......
  • 汉明权重(Hamming Weight)(统计数据中1的个数)VP-SWAR算法
    汉明权重(HammingWeight)(统计数据中1的个数)VP-SWAR算法定义汉明重量是一串符号中非零符号的个数。它等于同样长度的全零符号串的汉明距离(在信息论中,两个等长字符串之间的汉明距离等于两个字符串对应位置的不同字符的个数)。汉明重量在常见的数据位符号串中,它是1的个数。......
  • YC322A [ 20240724 CQYC NOIP 模拟赛 T4 ] 庫的 序计数(counting)
    题意给定一棵树\(T\),每次操作在某个点下方接上\(k\)个儿子。询问期望多少次排列,使得\(a_{fa_i}<a_i\)。保证\(k\)是偶数,对\(65536\)取模。\(n\le10^5,k\le2\times10^9\)。Sol考虑假如已经确定了一棵树的形态,如何求出最终的答案?可以发现对于每一个节点......
  • 计数调用装饰器 - 为什么我将函数属性重置回 0?
    下面的代码计算了装饰函数func被调用的次数:fromfunctoolsimportwrapsdefcounting_calls(func):@wraps(func)definner(*args,**kwargs):inner.call_count+=1returnfunc(*args,**kwargs)inner.call_count=0returninner......
  • 《埃尔登指环》死亡计数器
    我正在尝试制作自己的死亡计数器埃尔登戒指,我已经制作了一个手动计数应用程序,但我想自动化该过程,或者有一个脚本,如下面的站点,它将打开一个窗口,其中我还需要加载(A最好自动确定保存位置-并计算死亡人数);问题是:制作统计死亡人数的脚本的最佳方法是什么?读取游戏内存?但是我怎样才能......
  • 基于YOLOv8的汽车跟踪计数(创新点,功能实现保姆级教程)
    效果如视频所示:  YOLOV8github地址:GitHub-ultralytics/ultralytics:NEW-YOLOv8......
  • ref和reactive分别编写的计数器
    使用ref函数和reactive函数写的技术器小程序,ref的实现用到了reactive,推荐使用ref,代码点击查看代码<script>//setup是组合是API的体现import{reactive,ref}from'vue'exportdefault{setup(){conststatus=reactive({count:0})......
  • Java 经典排序算法代码 + 注释分析(冒泡、选择、插入、希尔、快排、计数、堆排、归并)
    Java经典排序算法代码+注释分析(冒泡、选择、插入、希尔、快排、计数、堆排、归并)以下是八种经典排序算法的代码,Java8亲测可用,可以直接运行importjava.util.Arrays;publicclassSort{privatestaticfinalint[]nums={3,44,38,5,47,15,36,26,27......
  • 有限背包计数问题
    https://class.51nod.com/Html/Textbook/ChapterIndex.html#chapterId=335&textbookId=126https://class.51nod.com/Html/Challenge/Problem.Html#problemId=1597如有限背包计数问题发现对于物品\(i\)最多填充\(i*i\),而对于\(i>\sqrtn\)可以视为完全背包,所以我们分为两类......