HDU6184 Counting Stars（三元环计数）_hstar计数

题意：
$\ \ \ \ \ \ \ \ $一幅$n$个点$m$条边的无向图， 问有多少对有公共边的单元环。
思路：
$\ \ \ \ \ \ \ \ $做法就是建立好图之后， 枚举每条边，枚举到$(u, v)$的时候， 如果$v$的度数大于$\sqrt m$，则暴力枚举$u$剩余的点， 因为度数大于$\sqrt m$的点不会超过$\sqrt m$个，这部分的时间复杂度是$O(m\sqrt m)$，如果$v$的度数小于$\sqrt m$，那么暴力枚举$v$连接的点，这样$v$连接的点不超过$\sqrt m$个， $v$这样的点最多$m$个，所以时间复杂度也是$\sqrt m$。
$\ \ \ \ \ \ \ \ $有个快点的做法就是：度数小的点往度数大的点连接有向边，相同则编号小的往编号大的连边，这样每个点的出度不超过$\sqrt n$，时间复杂度可以到$m\sqrt n$。
做法1：

#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 1e5 + 10;
const int maxm = 4e5 + 113;
using namespace std;

int n, m, T, kase = 1;
vector<int> G[maxn];
int cnt, du[maxn];
int vt[maxn], vis[maxn];

ll hash_table[maxm], top;
int nxt[maxm], head[maxm];

void __insert(ll val) {
    ll ans = val % maxm;
    nxt[top] = head[ans];
    head[ans] = top;
    hash_table[top] = val;
    top++;
}

bool get_count(ll val) {
    ll ans = val % maxm;
    int t = head[ans];
    while(~t) {
        if(hash_table[t] == val) return true;
        t = nxt[t];
    }
    return false;
}


int main() {
    while(scanf("%d %d", &n, &m) != EOF) {
        memset(nxt, -1, sizeof nxt);
        top = 0;
        memset(head, -1, sizeof head);
        for(int i = 0; i < maxn; i++) { G[i].clear(); du[i] = vis[i] = vt[i] = 0; }
        for(int i = 1; i <= m; i++) {
            int u, v; scanf("%d %d", &u, &v);
            //st.insert(u + (ll)v * n);
            //st.insert(v + (ll)u * n);
            __insert(u + (ll)v * n);
            __insert(v + (ll)u * n);
            G[u].push_back(v); G[v].push_back(u);
            du[u]++; du[v]++;

        }
        cnt = sqrt(m) + 1;
        ll ans = 0;
        ///统计每条边能形成多少个三元环， 最终结果是∑ C(tot, 2)
        for(int i = 1; i <= n; i++) {
            vis[i] = 1;
            for(int j = 0; j < G[i].size(); j++) vt[G[i][j]] = i;
            for(int j = 0; j < G[i].size(); j++) {
                ll tot = 0; int v = G[i][j];
                if(vis[v]) continue;
                if(du[v] <= cnt) {
                    for(int k = 0; k < G[v].size(); k++) if(vt[G[v][k]] == i) tot++;
                } else {
                    for(int k = 0; k < G[i].size(); k++) if(get_count((ll)v * n + G[i][k])) tot++;
                }
                ans += tot * (tot - 1) / 2;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
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
69
70
71

做法2：

#include<bits/stdc++.h>
typedef long long ll;
const int maxn = 1e5 + 10;
const int maxm = 2e5 + 113;
using namespace std;

typedef pair<int, int> pa;
int n, m, T, kase = 1;
int cnt, du[maxn], id[maxm];
int vt[maxn], vis[maxn];
ll tal[maxm];
int nxt[maxm], head[maxn], mp[maxm], top;
int x[maxm], y[maxm];

void add_edge(int u, int v, int di) {
    nxt[top] = head[u];
    head[u] = top;
    id[top] = di;
    mp[top] = v;
    top++;
}

//void __insert(ll val, int ix) {
//    ll ans = val % maxm;
//    nxt[top] = head[ans];
//    head[ans] = top;
//    hash_table[top] = val;
//    id[top] = ix;
//    top++;
//}
//
//int get_count(ll val) {
//    ll ans = val % maxm;
//    int t = head[ans];
//    while(~t) {
//        if(hash_table[t] == val) return id[t];
//        t = nxt[t];
//    }
//    return -1;
//}

void read(int &x){
    x = 0;
    char c = getchar();
    while(c < '0' || c > '9')  c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
}

int main() {
    while(scanf("%d %d", &n, &m) != EOF) {
        //for(int i = 0; i < maxn; i++) { G[i].clear(); du[i] = 0; vt[i] = 0; }
        //for(int i = 1; i <= n; i++) { G[i].clear();  du[i] = 0; vt[i] = 0; }
        for(int i = 1; i <= n; i++) { du[i] = vt[i] = 0; head[i] = -1; }
        top = 0; nxt[0] = -1;
        for(int i = 1; i <= m; i++) {
            //scanf("%d %d", &x[i], &y[i]);
            read(x[i]); read(y[i]);
            nxt[i] = -1; tal[i] = 0;
            //if(u > v) swap(u, v);
            //__insert(v + (ll)u * n, i);
            //G[u].push_back(pa(v, i));
            du[x[i]]++; du[y[i]]++;
        }
        for(int i = 1; i <= m; i++) {
            int u = x[i], v = y[i];
            if(du[u] > du[v]) add_edge(v, u, i);
            else if(du[v] > du[u]) add_edge(u, v, i);
            else {
                if(u > v) add_edge(v, u, i);
                else add_edge(u, v, i);
            }
        }
        ll ans = 0;
        for(int i = 1; i <= m; i++) {
            int u = x[i], v = y[i];
            int j = head[u];
            while(~j) { vis[mp[j]] = id[j]; vt[mp[j]] = u; j = nxt[j]; }
            j = head[v];
            while(~j) {
                int i1 = id[j];
                int nt = mp[j];
                if(vt[nt] == u) { tal[i]++; tal[i1]++; tal[vis[nt]]++; }
                j = nxt[j];
            }
        }
        for(int i = 1; i <= m; i++) ans += tal[i] * (tal[i] - 1) / 2;
        cout << ans << endl;
    }
    return 0;
}



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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94