大红数星星图论 XD网络赛

问题 A: 大红数星星

时间限制: 3 Sec 内存限制: 128 MB
提交: 1066 解决: 67
[提交][状态][讨论版]

题目描述

“三角形十分的美丽，相信大家小学就学过三角形具有稳定性，三角形也是二维几何中最基本的必不可少的元素之……”，大红走在路上若有所思，突然抬头看到了天空中有很多很亮的星星划过，星星和他们划过的轨迹像极了一个无向图。于是好学的大红，就开始数起了“三角形”，1、2、3……数了好久，大红数的眼泪都掉下来了，所以他哭着请求你来帮他，你这么好心一定不会拒绝吧！大红的三角形的定义：如果存在这样的三个边(A,B)、(B,C)、(A,C)（无向边），则算一个三角形。
大红会告诉你这个图G=(V,E),点数（星星个数）n和边数（轨迹个数）m以及每条边的两个点。

两个三角形不同是：当对于两个三角形的边，某个三角形存在一条边在另一个三角形的边中无法找到！

输入

多组数据。
第一行一个整数T<=10表示数据组数。
对于每组数据的第一行n表示星星个数，m表示星星划过的轨迹的个数，
接下来m行表示每个星星划过的轨迹的端点x,y(1<=x,y<=n)。
1<=n<=100000,1<=m<=min(100000,n*(n-1)/2)

输出

对于每组数据输出一个整数，表示三角形的个数。

样例输入

样例输出

#include<iostream>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<vector>

#include<cmath>

#include<map>

#include<set>

#include<fstream>

#include<memory>

#include<string>

using namespace std;

typedef long long LL;

#define MAXN  100003

#define INF 1000000009

/*

寻找三角形的个数

思路：

1. 枚举所有边，然后枚举边上两个点中度比较小的 那个点中包含可以到达 枚举的边中另一点的边 +1

最后/3

2. 先把所有点按照度的大小排序，然后用数组记录一个点可以到达的顶点(要求顶点的度大于它)

然后枚举每条边，找两个顶点的公共元素数目

*/

vector<int> E[MAXN];

vector<int> cnt[MAXN];

struct edge

{

    int f, t;

};

int T, n, m;

vector<edge> a;

int main()

{

    edge tmp;

    int f, t;

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d%d", &n, &m);

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

        {

            E[i].clear();

        }

        a.clear();

        int sum = ;

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

        {

            scanf("%d%d", &tmp.f, &tmp.t);

            E[tmp.f].push_back(tmp.t);

            E[tmp.t].push_back(tmp.f);

            a.push_back(tmp);

        }

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

        {

            sort(E[i].begin(), E[i].end());

        }

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

        {

            for (int j = ; j < E[i].size(); j++)

            {

                if (E[E[i][j]].size() > E[i].size())

                    cnt[i].push_back(E[i][j]);//可以到达的顶点 在这里保证顶点的度大于它的度

            }

        }

        for (int i = ; i < m; i++)//枚举所有边，找两个顶点的公共点个数

        {

            f = a[i].f, t = a[i].t;

            int s1 = E[f].size(), s2 = E[t].size();

            int z = , y = ;

            while (z < s1&&y < s2)

            {

                if (E[f][z] < E[t][y])

                {

                    z++;

                }

                else if (E[f][z] > E[t][y])

                {

                    y++;

                }

                else

                {

                    z++; y++; sum++;

                }

            }

        }

        printf("%d\n", sum / );

    }

}

星星