第二题 题解

· · 题解

首先可以想到，先对于所有的连通块进行计算贡献

运用乘法原理，将每个连通块的贡献相乘

定义一个连通块的贡献为它的可行方案数，下面开始分类讨论

对于存在环的连通块

这边发现，右边的环中，每个点都必须收入一条边，有两种可行方案

所以 4 号点所连接的唯一一条边，必须与 4 号点分为一组，有一种可行方案

易得：对于一个连通块，若块中存在环，则贡献为 2

对于不存在环的连通块

可以发现，这类连通块有 n 个点，n-1 条边

一定存在一个点是没有被分到边的

在 n 个点中选取 1 个没有被分到边的点，贡献为 C_n^1 = n

对于边数大于点数的连通块

一定存在一个边没有被分配到点，不符合要求，方案为 0。

所以遇到这种连通块时，直接全局判 0 即可。

现在问题转化为了：对于每个连通块，判断是否存在环，及点数与边数的关系

对于判环，也可以转化为点数与边数的关系：

随便作一个环，就可以发现，环中的点数 = 边数

而边数可通过 \text{所有点的出度入度之和} / 2 得出

整理得到：

对于每一个连通块：
   点数 > 边数： 为无环，贡献为点数
   点数 = 边数： 为有环，贡献为 2
   点数 < 边数： 不可行，答案为 0

最后将每个连通块的贡献相乘即可

代码：

#define loop(i,x,y) for(int i=x;i<=y;i++)
#define doop(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const int Mod=1000000007;
const long long N=1e6+5;
ll n,m,xx,yy;
ll to[N],hd[N],nxt[N],tot;
void add(ll u,ll v){
    nxt[++tot]=hd[u];
    to[tot]=v;
    hd[u]=tot;
}
ll edg,pts;
void dfs(ll p){
    vis[p]=1,pts++;
    for(int i=hd[p];~i;i=nxt[i],edg++){
        if(!vis[to[i]]) dfs(to[i]);
    }
}
signed main(){
    memset(hd,-1, sizeof hd);
    n=read(),m=read();
    loop(i,1,m){
        xx=read(),yy=read();
        add(xx,yy),add(yy,xx);
    }
    ll ans=1;
    loop(i,1,n){

        if(!vis[i]){
            pts=edg=0;
            dfs(i);
            if(pts>edg/2) ans=(ans*pts)%Mod;
            else if(pts==edg/2) ans=(ans*2)%Mod;
            else {ans=0;break;}
        } 
    }
    cout<<ans;
    return 0;
}