JZOI【NOI2017模拟3.30】輪回

Description

掌管着世界的暗流的是一個叫做Samjia的人。

他看到所有人的生死，他看見所有人一世又一世的輪回，而他卻從未把握過自己的命。

在無法估計的命中，他看見那些輪回，他很好奇，這一切的一切，都是如何開始如何結束，他想，就算是他也會堕入這樣的輪回中的吧。

于是他開始數輪回，他看到的是一個有n個點m條邊的無向圖（邊是帶标号的），一個輪回是一個由四條邊組成的環，環中不能有重複的邊，除了起點和終點外（當然，由于是一個環，起點和終點是一樣的）不能經過一個同樣的點多次。兩個輪回被視為不同的當且僅當兩個輪回各自的4條邊中有一條的編号不同，Samjia想知道，這個system中有多少不同的輪回。

他忙着思考人生，是以數輪回的任務就交給你了。

Input

第一行兩個數n和m分别表示點的個數和邊的條數。

接下來m行每行兩個數x和y表示x和y之間一條無向邊

保證無重邊和自環。

Output

一行一個數，表示圖中輪回的個數，輪回的定義見題目描述。

Sample Input

4 6

1 2

2 3

3 4

4 1

1 3

2 4

Sample Output

3

樣例說明

有三個不同的輪回：

1、1–>2–>3–>4–>1

2、1–>3–>2–>4–>1

3、1–>2–>4–>3–>1

Data Constraint

對于30%的資料1<=n,m<=200

對于50%的資料1<=n,m<=1000

對于100%的資料1<=n<=50000 1<=m<=100000

保證無重邊和自環。

比賽的時候沒有多想，直接打了個50分走人，感覺100分又是什麼神奇算法。。

結果發現資料神奇水，一堆人水過，而且這還是出題人（samjia）專門構造的。。結果還是被水過。。

正解的話要用到一個神奇的結論，來自CF378D。

就是，枚舉與一個點相連，且度數大于它的點，時間複雜度是根号的。

那麼基于這個思路，然後考慮一個大小為4的環，它的度數順序有三種情況，如果把無向邊變成度數小的連向度數大的，就會出現神奇的玩意。。

什麼神奇的玩意呢。。

度數最大的點，有兩個連向他的邊，對于這種，我們直接枚舉它對面那個點，然後枚舉對于原圖和它相連的邊，符合就更新咯。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std; 
const int N=+;
typedef long long ll;
ll ans;
int n,m,tot;
int head[N],go[N],next[N];
int d[N],id[N],p[][],f[N],b[N];
int v[N];
struct node
{
    int x,y;
}a[N];
bool cmp(node a,node b)
{
    return a.x<b.x;
}
inline void add(int x,int y)
{
    go[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
}
int main()
{
    freopen("palingenesis.in","r",stdin); 
    freopen("palingenesis.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,,m)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        d[x]++;
        d[y]++;
    }
    fo(i,,n)
    {
        a[i].x=d[i];
        a[i].y=i;
    }
    sort(a+,a++n,cmp);
    fo(i,,n)id[a[i].y]=i;
    fo(i,,n)
    {
        int j=head[i];
        while (j)
        {
            int v=go[j];
            if (id[v]>id[i])p[i][++b[i]]=v;
            j=next[j];
        }
    }
    fo(i,,n)
    {
        int j=head[i];
        while (j)
        {
            int y=go[j];
            fo(k,,b[y])
            {
                int x=p[y][k];
                if (id[x]<=id[i])continue;
                if (v[x]<i)v[x]=i,f[x]=;
                else ans+=f[x],f[x]++;
            }
            j=next[j];
        }
    }
    printf("%d\n",ans);
}