统计无向图中三角形的个数，复杂度m*sqrt(m).

统计无向图中三角形的个数，复杂度m*sqrt(m).

#include<stdio.h>

#include<vector>

#include<set>

#include<math.h>

#include<algorithm>

using namespace std;

#define LL long long

vector<int> G[];

set<LL> st;

int vis[], link[], out[];

int main(void)

{

    LL ans, sum;

    int n, i, j, m, k, x, y, z, B;

    while(scanf("%d%d", &n, &m)!=EOF)

    {

        B = sqrt(m);

        st.clear();

        for(i=;i<=n;i++)

        {

            G[i].clear();

            vis[i] = out[i] = link[i] = ;

        }

        for(i=;i<=m;i++)

        {

            scanf("%d%d", &x, &y);

            G[x].push_back(y), out[x]++;

            G[y].push_back(x), out[y]++;

            st.insert((LL)x*n+y);

            st.insert((LL)y*n+x);

        }

        ans = ;

        for(i=;i<=n;i++)

        {

            x = i;

            vis[x] = ;

            for(j=;j<G[x].size();j++)

                link[G[x][j]] = x;

            for(j=;j<G[x].size();j++)

            {

                sum = ;

                y = G[x][j];

                if(vis[y])

                    continue;

                if(out[y]<=B)

                {

                    for(k=;k<G[y].size();k++)

                    {

                        z = G[y][k];

                        if(link[z]==x)

                            sum++;

                    }

                }

                else

                {

                    for(k=;k<G[x].size();k++)

                    {

                        z = G[x][k];

                        if(st.find((LL)z*n+y)!=st.end())

                            sum++;

                    }

                }

                ans += sum*(sum-)/;

            }

        }

        printf("%lld\n", ans);

    }

}