首页 > 编程语言 >算法随笔——图论:无向图三/四元环计数

算法随笔——图论:无向图三/四元环计数

时间:2024-03-05 23:12:45浏览次数:33  
标签:图论 int long 四元 无向 https getchar define

参考:https://oi-wiki.org/graph/rings-count/

题目链接:P1989 无向图四元环计数

求四元环步骤:

  1. 建双向边。
  2. 给每条边定向,由度数小的点指向大的,若度数一样则看编号大小。
  3. 此时只有这几种情况:image

都可以归类为:
image

  1. 枚举起始点 A,枚举 A <--> B(双向边),枚举 B --> C,让 C 点被访问次数 \(cnt\) 加 \(1\)。
  2. 四元环数量即为 \(cnt[i]*(cnt[i]-1) / 2\)

时间复杂度 \(O(n \sqrt n)\)。

具体复杂度证明和三元环求解见 OI WIKI。

代码

// Problem: #191. 无向图四元环计数
// Contest: LibreOJ
// URL: https://loj.ac/p/191
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Author: Eason
// Date:2024-02-24 18:13:33
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define il inline
#define gc getchar
inline int read() {
    int f = 1, k = 0;
    char c = getchar();

    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;

        c = getchar();
    }

    while (c >= '0' && c <= '9')
        k = (k << 1) + (k << 3) + (c ^ 48), c = getchar();

    return k * f;
}
const int N = 2e5 + 5;
int n, m, deg[N];
vector<int> v[N], v1[N];
int cnt[N];
int main() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u =  read(), v = read();
        v1[u].push_back(v);
        v1[v].push_back(u);
        deg[u] ++, deg[v] ++;
    }

    for (int i = 1; i <= n; i++)
        for (int j : v1[i])
            if (deg[i] < deg[j] || (deg[i] == deg[j] && i < j))
                v[i].push_back(j);

    int res = 0;

    for (int i = 1; i <= n; i++) {
        for (int j : v1[i])
            for (int k : v[j])
                if (deg[i] < deg[k] || (deg[i] == deg[k] && i < k))
                    res += cnt[k]++;

        for (int j : v1[i])
            for (int k : v[j])
                cnt[k] = 0;
    }

    cout << res << endl;
    return 0;
}
// Problem: P1989 无向图三元环计数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1989
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Author: Eason
// Date:2024-02-24 18:06:06
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define il inline
#define gc getchar
inline int read()
{
	int f=1,k=0;
	char c = getchar();
	while (c <'0' || c > '9')
	{
		if (c=='-') f=-1;
		c=getchar();
	}
	while(c >= '0' && c <= '9')  k = (k << 1)+(k << 3)+(c^48),c=getchar();
	return k*f;
}
const int N = 2e5+5;
int n,m,deg[N];
vector<int> v[N],v1[N];
bool vis[N];
int main()
{
	cin >> n >> m;
	for (int i = 1;i <= m;i++)
	{
		int u = read(),v = read();
		v1[u].push_back(v);v1[v].push_back(u);
		deg[u]++,deg[v]++;
	}
	for (int i = 1;i <= n;i++)
		for (auto j : v1[i])
			if (deg[i] < deg[j] || (deg[i] == deg[j] && i < j)) v[i].push_back(j);
	int cnt = 0;
	for (int i = 1;i <= n;i++)
	{
		for (int j :v[i]) vis[j] = 1;
		for (int j:v[i])
			for (int k : v[j]) if (vis[k]) cnt++;
		for (int j :v[i]) vis[j] = 0;
	}
	cout << cnt << endl;	
	return 0;
}

标签:图论,int,long,四元,无向,https,getchar,define
From: https://www.cnblogs.com/codwarm/p/18030480

相关文章

  • dp&图论 杂题选做
    开个新坑qwq。upd:CSP前一周暂时停更。upd:暂时不会更了。P1099经典套路题。算法一:枚举。先dfs求出树的直径,再枚举直径上的每条路径,再dfs一遍求出最小偏心距即可。时间复杂度\(O(n^3)\),足以通过本题(由此可见本题有多水)。算法二:双指针。通过观察可以发现,在固定左端......
  • 【学习笔记】《综述图论中连通性及相关问题的一些处理方法》
    2023集训队论文第一篇。发现好像存在很多我不会/见过但是从来没记住过的结论之类的,所以这篇主要是背结论用的。目录无向图双连通性点双连通分量的性质耳分解割空间与环空间有向图可达性问题强连通性有向环竞赛图记\(u\rightsquigarrowv\)为\(u\)到\(v\)的路径,\(u\t......
  • Pursuit For Artifacts 题解(图论)
    PursuitForArtifacts题解题目给定一张\(n\)个点\(m\)条边的简单无向连通图,边有边权,边权要么为\(0\),要么为\(1\)。每条边只能通过一次(两个方向加起来只能通过一次)。求是否存在一条从\(a\)到\(b\)的路径,满足路径上至少存在一条权为\(1\)的边。\(1\leqn,m\l......
  • 图论算法汇总
    图论算法在信息学竞赛中有着非常广泛的应用,也频繁在考试与比赛中作为重要的考察知识.本文汇总并分类了信息学竞赛中的图论算法.1生成树与最短路1.1Prim算法Prim算法可以求出一张图的最小生成树,时间复杂度为\(\mathcal{O}((|V|+|E|)\log|V|)\).memset(dis,0x3f,sizeo......
  • 2024-02-24:用go语言,给你一个 n 个点的带权无向连通图,节点编号为 0 到 n-1, 同时还有一
    2024-02-24:用go语言,给你一个n个点的带权无向连通图,节点编号为0到n-1,同时还有一个数组edges,其中edges[i]=[fromi,toi,weighti],表示在fromi和toi节点之间有一条带权无向边,最小生成树(MST)是给定图中边的一个子集,它连接了所有节点且没有环,而且这些边的权值和最......
  • 图论——树有关知识
    树的遍历顺序有关前序,中序,后序概念自行百度。知道几种顺序来确定二叉树形态首先先明确一点至少要知道两种顺序以上才能确定一个树,因为如果只知道前序或者后序就只能确定根节点,而不能确定根节点的左右子树。但如果知道中序,那就不能确定根节点。然后如果知道两种顺序的话,必须要......
  • Codeforces 图论题
    CF243BHydra枚举点\(u,v\),或者说枚举边。然后找出\(u,v\)分别所连的点。有数组\(st\),结点\(x\)仅与\(u\)相邻则\(st[x]=1\),仅与\(v\)相邻则\(st[x]=2\),与两个点都相邻则\(st[x]=3\)。用数组\(rest\)记录\(st[x]=3\)的所有\(x\)。先优先选走至多\(h\)个\(......
  • 【图论】基环树 学习笔记
    基环树下面几个条件互相等价:一个图(连通块)是基环树联通块有n个点n条边图上存在且仅存在一个环,且环上每个节点是一颗子树的根。通常情况下树指的都是无向图,但是有向图也可以构成基环树。内向基环树:每个点都有一条出边。容易发现沿着这条边一定会走到环上“向内走”。外......
  • 图论
    图论Part1图Part1.1简介一张图$G$由若干个点和连接这些点的边构成。称点的集合为点集$V$,边的集合为边集$E$,记$G=(V,E)$。Part1.2图的种类图大体上分为两种:边没有指向性的图称为无向图,有指向性的图称为有向图。我们可以给点和边赋予属性,例如权值(cost)。边上带有......
  • 找负环(图论基础)
    目录负环spfa找负环方法一方法二实际效果负环环内路径上的权值和为负。spfa找负环两种基本的方法统计每一个点的入队次数,如果一个点入队了n次,则说明存在负环统计当前每个点中的最短路中所包含的边数,如果当前某个点的最短路所包含的边数大于等于n,也说明存在负环实际上两......