Counting Stars HDU - 6184[三元环计数]_三元环计数板子题

题目：

给你一个图，求有多少不同的由两个三元环拼起来的图形。

分析：

三元环计数题，考虑每个边的贡献，设num = 每个边参与构成的图形数，则贡献为num * (num - 1) / 2，注意用链式前向星来存边的贡献。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;//三年竞赛一场空，不开long long见祖宗 
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
#define x first
#define y second
typedef pair<int, int> par;
const ll mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
struct edge
{
    int ep, val, nex;
    edge(int ep = 0, int val = 0, int nex = 0) : ep(ep), val(val), nex(nex){}
}e[maxn << 1];
int tot, head[maxn];
void init() { mem(head, -1), tot = 0; }
void addedge(int x, int y, int val) { e[tot] = edge(y, val, head[x]); head[x] = tot++;}

par a[maxn];
int d[maxn];
int vis[maxn];
ll num[maxn];
int pre[maxn];
int n, m; 

int main()
{
    while(cin >> n >> m)
    {
        init();
        mem(d, 0), mem(num, 0), mem(vis, 0), mem(pre, 0);
        for(int i = 1; i <= m; i++)
            cin >> a[i].x >> a[i].y, d[a[i].x]++, d[a[i].y]++;
        for(int i = 1; i <= m; i++)
        {
            int x = a[i].x, y = a[i].y;
            if(d[x] > d[y] || d[x] == d[y] && x > y) swap(x, y);
            addedge(x, y, 1);
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = head[i]; ~j; j = e[j].nex)
            {
                int u = e[j].ep;
                vis[u] = i;
                pre[u] = j;
            }
            for(int j = head[i]; ~j; j = e[j].nex)
            {
                int u = e[j].ep;
                for(int k = head[u]; ~k; k = e[k].nex)
                {
                    int v = e[k].ep;
                    if(i == vis[v])
                        num[j]++, num[k]++, num[pre[v]]++;
                }
            }
        }
        ll res = 0;
        for(int i = 0; i <= tot; i++)
            res += num[i] * (num[i] - 1) / 2;
        cout << res << endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68