HDU 6184 Counting Stars 经典三元环计数

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6184

题意:

n个点m条边的无向图,问有多少个A-structure

其中A-structure满足V=(A,B,C,D) && E=(AB,BC,CD,DA,AC)

解法:

可以看出A-structure是由两个有公共边的三元环构成的,然后就变成了这道题。

http://www.cnblogs.com/spfa/p/7495438.html

#include <stdio.h>
#include <set>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100005;
typedef long long LL;
vector <int> G[maxn];
set <LL> s;
int n, m, vis[maxn], linker[maxn], out[maxn]; int main()
{
while(scanf("%d %d", &n, &m) != EOF)
{
s.clear();
for(int i=1; i<=n; i++){
vis[i] = out[i] = linker[i] = 0;
G[i].clear();
}
for(int i=1; i<=m; i++){
int x, y;
scanf("%d %d", &x,&y);
G[x].push_back(y),out[x]++;
G[y].push_back(x),out[y]++;
s.insert((LL)x*n+y);
s.insert((LL)y*n+x);
}
int B = sqrt(m);
LL ans = 0;
for(int i=1; i<=n; i++){
int x = i, y;
vis[x] = 1;
for(int j=0; j<G[x].size(); j++) linker[G[x][j]] = x;
for(int j=0; j<G[x].size(); j++){
LL sum = 0;
y = G[x][j];
if(vis[y]) continue;
if(out[y]<=B){
for(int k=0; k<G[y].size(); k++){
int z = G[y][k];
if(linker[z]==x) sum++;
}
}else{
for(int k=0; k<G[x].size(); k++){
int z = G[x][k];
if(s.find((LL)z*n+y) != s.end()) sum++;
}
}
ans = ans + sum*(sum-1)/2;
}
}
printf("%lld\n", ans);
}
return 0;
}
上一篇:sql 增加字段


下一篇:poj 1035KINA Is Not Abbreviation