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);
}