【HDU-6184】Counting Stars【三元环+set+hash+邻接表】

【HDU-6184】Counting Stars【三元环+set+hash+邻接表】

问题链接:https://vjudge.net/problem/HDU-6184

Solution:

题目要求寻找 “A-structure”,其实就是有一条公共边的两个三元环的组数。

这道题需要暴力枚举每一条边,即假设它是那条三元环的公共边,看看能构成几个三元环,显然如果只能构成1个三元环,则无法组成”A-structure”,至少需要两个三元环。如果对于一个公共边能够找到\(cnt\)个三元环,则任意两个都能构成一个“A结构”,所以只要用组合数学中的方法计算一下\(cnt \times (cnt – 1) / 2\)就可以。

不过,直接根据输入的顺序进行暴力是会超时的,需要调整一下枚举边的顺序。无论采用哪种办法,只要保证最后枚举边的顺序依此枚举完与一个点的所有边后再枚举下一个顶点就可以。很多人博客中采取的是用循环结构枚举顶点,之后通过一个vis[]数组来判重,如果发现一个点已经遍历过,枚举之后的点时就不必考虑这个顶点了。而我下边的代码采用了对边排序的方法【注:但是需要保证每条边在存储时,较小的顶点固定放在一个变量上,之后根据这个变量来排序】,之后直接枚举每条边,最后的结果是,这个遍历顺序和上边枚举顶点的遍历顺序完全一样。

有序搜索带来的好处是,一个点相连的全部边一定连着这个点(这是显然的),于是我们可以在遍历与这个点相连的全部边时提前开一个linked[]数组,将与该点相连的所有顶点在这个数组中的值设置成该点的值,这样,枚举一个边的时候,如果使用不是该点的顶点判断三元环,就可以直接使用这个数组判断一下与它相连的所有点的值,来确定是否构成了三元环【这段表述起来有些不易于阅读,可以结合代码来看】。

很多博客中所写的题解,通过使用一个sqrt(m)来判断应该使用哪个点枚举边,但是其实可以不使用这个,只要判断一下,两个边的度数哪个小就枚举哪个顶点的边就好。【备注:m是边数,对于一个n阶无权无项图,它的大小(即边的个数)最多是\(\frac{n \times (n – 1)}{2}\),即n近似等于\(\sqrt{m}\)】

简单地说,枚举到一条边的 时候就决定一下使用这条边的哪个顶点来判三元环【因为判断三元环要判断与一个点相连的其它点是否能连回当前枚举边的另一个顶点,所以当然是枚举那个度数小的顶点要快一些】,如果使用最近这几次枚举的边共同连接的一个点的话,就直接借助linked数组,\(O(1)\)复杂度,反之就是用hash值+set判重。

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
// #define DBG

using namespace std;

const int LIM = 1e5 + 5;
typedef long long LL;
struct edge {
    int x, y;
    bool operator < (const edge &e) const { return x < e.x; }
} edges[LIM * 2];
vector<int> v[LIM];
set<LL> e;
int linked[LIM];
int n, m;
LL ans;

/* 用来计算hash值,结合set,可以用来快速判断是否存在某条边 */
inline LL myHash(LL x, LL y) {
    return x + y * (n + 1);
}

inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

inline void init() {
    for (int i = 1; i <= n; i++)
        v[i].clear();
    memset(edges, 0, sizeof edges);
    memset(linked, 0, sizeof linked);
    e.clear();
    ans = 0;
}

LL getSum(int x, int y) {
    LL cnt = 0;
    /* 分类优化在这道题中很重要,对于顶点y的度小于x的度的情况,可以直接使用刚刚根据x打好的linked数组 */
    if (v[y].size() <= v[x].size()) {
        for (vector<int>::iterator ite = v[y].begin(); ite != v[y].end(); ite++)
            if (linked[*ite] == x) cnt++;
    } else {
        /* 对于y顶点的度大于x顶点度的情况,使用set配合hash值查询 */
        for (vector<int>::iterator ite = v[x].begin(); ite != v[x].end(); ite++)
            if (e.find(myHash(*ite, y)) != e.end()) cnt++;
    }
#ifdef DBG
    printf("Edge: (%d, %d) -> cnt: %d\n", x, y, cnt);
#endif
    /* 如果一条边有cnt个三元环,根据组合数学,应当会有cnt * (cnt - 1) / 2个题设结构 */
    /* 需要注意cnt * (cnt - 1)可能会超过int的取值范围 */
    return cnt * (cnt - 1) / 2;
}

int main(void) {
    while (~scanf("%d%d", &n, &m)) {
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &edges[i].x, &edges[i].y);
            e.insert(myHash(edges[i].x, edges[i].y));
            e.insert(myHash(edges[i].y, edges[i].x));
            v[edges[i].x].push_back(edges[i].y);
            v[edges[i].y].push_back(edges[i].x);
            /* 如果输入的第二个顶点小于第一个顶点,进行交换,为了维护我们需要的顺序 */
            if (edges[i].x > edges[i].y) swap(edges[i].x, edges[i].y);
        }
        /* 将边按照x进行排序,edges数组中的边将会变得有序 */
        sort(edges, edges + m);
        int pre = 0;
        for (int i = 0; i < m; i++) {
            if (edges[i].x != pre) {
                pre = edges[i].x;
                /* 得益于有序,我们可以预先根据x值将与它相邻的顶点在linked数组的值设为x */
                for (vector<int>::iterator ite = v[edges[i].x].begin(); ite != v[edges[i].x].end(); ite++)
                    linked[*ite] = edges[i].x;
            }
#ifdef DBG
            cout << "#################" << endl;
            for (int i = 1; i <= n; i++) {
                printf("# linked[%d] = %d #\n", i, linked[i]);
            }
            cout << "#################" << endl;
#endif
            ans += getSum(edges[i].x, edges[i].y);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

做题中间犯了一个小错误,导致三个小时一直在WA,事后发现这个错误真的不值一提,是一个十分粗心的错误,但是由于这个错误如果真疏忽的话可能会想不到这个点来,所以在这里记录一下,就是由于所有的顶点取值范围是1到n,所以清空邻接表的时候要从1到n进行clear(),我一开始失误地从0到n – 1进行了clear,刚好把顶点n的vector漏掉了。

最后附上一些自编的测试数据:

输入:

7 12
1 7
2 1
4 2
4 5
6 5
6 7
1 3
2 3
4 3
5 3
6 3
7 3

8 16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
5 6
7 8

2 1
1 2

5 6
1 2
2 3
3 1
1 4
1 5
5 4

7 11
1 3
1 2
2 3
3 4
2 4
5 4
5 2
6 4
6 5
6 7
7 5

5 5
1 3
3 4
4 5
5 1
3 5

 

输出:

6
30
0
0
4
1