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;

}