hud 6184

$n$ 点 $m$ 边的图求多少对三元环公用一条边
变无向图为有向图

建图方法:
对于每条无向边度数小的端点向度数大的端点连边
度数相同则编号小的点向编号大的点连边
这样就构成 $DAG$
遍历：
遍历每条边的 $u$
标记另一端点 $v$
遍历该边的 $v$
如果 $v$ 的 $v_2$ 的标记与 $v$ 相同
则说明构成了三元环 $(u, v), (v, v_2), (u, v_2)$

记录每条边构成的三元环的个数 $x$
组合数 $x \choose 2$ 加入答案

由于连边时每个点的出边都要 $<= \sqrt(m)$

所以时间复杂度 $O(m \sqrt(m))$

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <map>

#include <cstdlib>

using namespace std;

#define gc getchar()

inline int read() {

    int x = ; char c = gc;

    while(c < '' || c > '') c = gc;

    while(c >= '' && c <= '') x = x *  + c - '', c = gc;

    return x;

}

#undef gc

const int N = 1e6 + , M = 2e5 + ;

int du[N], a[M], b[M];

int n, m, head[N], cnt, Ans[N];

struct Node {int v, nxt, id;} G[M];

struct Node2 {int first, second;} vis[N];

inline void Add(int u, int v, int id) {

    G[++ cnt].v = v; G[cnt].nxt = head[u]; G[cnt].id = id; head[u] = cnt;

}

void Clear() {

    cnt = ;

    memset(vis, , sizeof vis);

    memset(du, , sizeof du);

    memset(Ans, , sizeof Ans);

    for(int i = ; i <= n; i ++) head[i] = -;

}

int main() {

    while(scanf("%d %d", &n, &m) == ) {

        Clear();

        for(int i = ; i <= m; i ++) {

            a[i] = read(), b[i] = read();

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

        }

        for(int i = ; i <= m; i ++) {

            if(du[a[i]] > du[b[i]] || (du[a[i]] == du[b[i]] && a[i] > b[i])) swap(a[i], b[i]);

            Add(a[i], b[i], i);

        }

        int use_num = ;

        for(int i = ; i <= m; i ++) {

            use_num ++;

            for(int j = head[a[i]]; ~ j; j = G[j].nxt) {

                vis[G[j].v] = (Node2) {use_num, G[j].id};

            }

            for(int j = head[b[i]]; ~ j; j = G[j].nxt) {

                if(vis[G[j].v].first == use_num) {

                    Ans[i] ++, Ans[G[j].id] ++, Ans[vis[G[j].v].second] ++;

                }

            }

        }

        long long answer = ;

        for(int i = ; i <= m; i ++) if(Ans[i] > ) answer += (Ans[i] * (Ans[i] - ) / );

        printf("%lld\n", answer);

    }

    return ;

}

巴特西

hud 6184

最新文章

热门文章