HDU-6184-counting Stars(広西招待試合C題)(データ構造最適化)

タイトルリンク
题意:あなたに1枚の図をあげて、それからあなたにいくつのA-データの构造の具体的な构造が1つの正方形の中で1本の线をプラスすることを闻きます.
考え方:すべての三元環を求めて、組み合わせます.具体的には、各エッジについて、このエッジと三角形を構成できる点をいくつ求めることです.そして組み合わせるといいですね.
具体的な操作:直接エッジを列挙して、それから各端点を列挙して、私は先にこのように列挙して、だめだと発見して、T.それから私たちは角度を変えて、すべての点を列挙して、それからすべての川という点に関する辺を列挙して、もしこの点が列挙されたら、列挙しなくてもいいので、多くの時間を節約することができます.また、ここでは小さな操作が使われていて、騒がしいです.1つのエッジが存在するかどうかを判断するために、直接手動でこのエッジをhashに与えることができます.コードを具体的に見る.

#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 

using namespace std;

#define pb push_back
#define pi acos(-1)

const long long mod = 1000000007;

#define maxn 111111
#define maxm 11111
vector<int> gg[maxn];
int vis[maxn];
int nex[maxn];
int out[maxn];
int n, m;
set<long long> ss;
int main()
{

    long long ans, tot;
    int limt;
    while(scanf("%d%d", &n, &m) != EOF) {
        int limt = sqrt(m);
        ss.clear();
        for(int i = 1; i <= n; i++) {
            gg[i].clear();
            vis[i] = out[i] = nex[i] = 0; //    
        }
        int x, y;
        for(int i = 1; i <= m; i++) {
            scanf("%d%d" , &x, &y);
            gg[x].pb(y); //   
            gg[y].pb(x);
            out[x]++;
            out[y]++;
            ss.insert((long long)x * n + y);  //hash 
            ss.insert((long long)y * n + x);
        }
        ans  = 0;
        int xx, yy, zz;
        for(int i = 1; i <= n; i++) {
            xx = i;
            vis[xx] = 1;
            for(int j = 0; j < gg[xx].size(); j++) 
                nex[gg[xx][j]] = xx;   //nex            ，             
            for(int j = 0; j < gg[xx].size(); j++) {
                tot = 0;
                yy = gg[xx][j];
                if(vis[yy]) continue;
                if(out[yy] <= limt) { //   yy       log(m)     ，      set  
                    for(int k = 0; k < gg[yy].size(); k++) {
                        zz = gg[yy][k];
                        if(nex[zz] == xx) tot++;
                    }
                }
                else {
                    for(int k = 0; k < gg[xx].size(); k++) {
                        zz = gg[xx][k];
                        if(ss.find((long long) zz * n + yy) != ss.end()) tot++;   //set  
                    }
                }
                ans += tot * (tot - 1) / 2;
            }

        }
        printf("%lld
", ans);

    }

    return 0;
}