这篇文章上次修改于 222 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
本文共 1326 个字，阅读时长 ≈ 4 分钟

P3043 [USACO12JAN] Bovine Alliance G

题目链接

题意

给出 n 个点 m 条边的无向图，要将所有边定向，且要求每个点的入度不大于 1，求可行方案数，对 $10^9+7$ 取模。

思路

考虑这个图单纯是一个环的情况，能发现对这个环定向的话只有两种情况，顺时针定向或者逆时针定向，那我们再向这个环上添加一条边指向另一个点使它变成一颗基环树呢？那这条边只有一种定向的可能，就是向那个单独的点定向。那如果把那条边指向的点换成一个环呢？你会发现这就是无解的情况，因为定向两个环的时候占用了所有的点，中间那条连接的边就没法定向了。

而如果这个图里没有环呢？那么定向的方案数就等于点数，因为一定会有一个点没有入度，定向的方案数即为选取这个点的方案数也就是 n。

最后一个要注意的点就是这个图不保证连通，可以运用乘法定理去统计所有连通块的总方案数。

然后知道了怎么做之后就是选择做法了呗，看了一圈题解发现没有并查集合并的做法（之前那个并查集的好像被撤了），那就讲讲并查集合并喽。

其实并查集合并就是在合并时同时合并这个连通块的信息，这里要统计的就是这个连通块里的边数和点。合并时要注意边数要加 1，也就是要把现在的这条边加进去。

上代码！

代码

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=100005,mod=1000000007;
int n,m;
int p[N],dian[N],bian[N];
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}//快读
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}//并查集找祖先
signed main()
{
    n=read(); m=read();
    //初始化并查集，记得初始化点数为1，也就是它自己
    for(int i=0;i<=n;++i) p[i]=i,dian[i]=1;
    for(int i=0;i<m;++i){
        int u=read(),v=read();
        u=find(u),v=find(v);
        //如果找到环的话就只增加边数
        if(u==v) ++bian[u];
        else{
            //否则合并，并合并边数和点数
            p[u]=v;
            dian[v]+=dian[u];
            dian[u]=0;
            //边数记得加1，也就是现在的这条边
            bian[v]+=bian[u]+1;
        }
    }
    int ans=1;
    for(int i=1;i<=n;++i){
        //找独立的连通块
        if(p[i]!=i) continue;
        //统计答案
        if(bian[i]<dian[i]) ans*=dian[i],ans%=mod;
        else if(bian[i]==dian[i]) ans<<=1,ans%=mod;
        else ans=0;
    }
    cout<<ans<<endl;
    return 0;
}