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

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

Solution:

#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 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);
e.clear();
ans = 0;
}

LL getSum(int x, int y) {
LL cnt = 0;
if (v[y].size() <= v[x].size()) {
for (vector<int>::iterator ite = v[y].begin(); ite != v[y].end(); ite++)
} 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;
for (vector<int>::iterator ite = v[edges[i].x].begin(); ite != v[edges[i].x].end(); ite++)
}
#ifdef DBG
cout << "#################" << endl;
for (int i = 1; i <= n; i++) {
}
cout << "#################" << endl;
#endif
ans += getSum(edges[i].x, edges[i].y);
}
printf("%lld\n", ans);
}
return 0;
}

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