有向图欧拉回路个数 BEST定理

有向图欧拉回路个数

BZOJ 3659 但是没有这道题了  直接贴一个别人的板子吧

欧拉回路：存在一条路径经过所有的边刚好1次

有向图欧拉回路存在充要条件：①图连通；②对于所有点都满足出度=入度

BEST 定理   https://en.wikipedia.org/wiki/BEST_theorem

定理没仔细看 这个东西感觉不需要搞得非常懂 定理而已。

我只记住了公式 tw(G)表示外向生成树个数，deg表示入度出度都一样 相等的嘛。

当然欧拉回路因为是回路所以存在循环同构，例如下图：

1->2；2->1；1->3；3->1

欧拉回路其实只有1种，但是如果算路径走法的话就会有2种

1 2 1 3 1 和 1 3 1 2 1

这个时候sum还要再乘上x点的出度

https://blog.****.net/popoqqq/article/details/77017325

https://blog.****.net/Jaihk662/article/details/79338437

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
#define mod 1000003
LL Jz[][], out[], jc[] = {};
int main(void)
{
    LL ans, A, B, P, temp;
    int n, i, j, k, m, x;
    for(i=;i<=;i++)
        jc[i] = jc[i-]*i%mod;
    while(scanf("%d", &n), n!=)
    {
        memset(Jz, , sizeof(Jz));
        for(i=;i<=n;i++)
        {
            scanf("%d", &m);
            out[i] = m;
            while(m--)
            {
                scanf("%d", &x);
                Jz[i][x]--, Jz[x][x]++;
            }
        }
        if(n== && out[]==)
        {
            printf("1\n");
            continue;
        }
        n -= ;
        for(i=;i<=n;i++)
        {
            for(j=;j<=n;j++)
                Jz[i][j] = (Jz[i+][j+]+mod)%mod;
        }
        ans = ;
        for(i=;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                if(Jz[j][i])
                    break;
            }
            if(j!=i)
            {
                ans = mod-ans;
                for(k=i;k<=n;k++)
                    swap(Jz[i][k], Jz[j][k]);
            }
            for(j=i+;j<=n;j++)
            {
                A = Jz[i][i], B = Jz[j][i];
                while(B)
                {
                    P = A/B, temp = A, A = B, B = temp%B;
                    ans = mod-ans;
                    for(k=i;k<=n;k++)
                    {
                        Jz[i][k] = (Jz[i][k]-P*Jz[j][k]%mod+mod)%mod;
                        swap(Jz[i][k], Jz[j][k]);
                    }
                }
            }
            ans = ans*Jz[i][i]%mod;
        }
        if(ans==)
        {
            printf("0\n");
            continue;
        }
        n += ;
        for(i=;i<=n;i++)
            ans = ans*jc[out[i]-]%mod;
        ans = ans*out[]%mod;
        printf("%lld\n", ans);
    }
    return ;
}
/*
3
2 2 3
1 1
1 1
*/