题解 P1657 【选书】

· · 题解

这题用图论完全可以O(n)做

首先建图：对于每个人，将他喜欢的两本书的编号连一条无向边

这样就得到了一个n个节点n条边的图，而每一个合法方案就是为每一条边选择一个方向，使得每个点的入度为1

然后考虑答案如何计算

证明：

（必要性）如果存在一个连通块，块内点的数量大于边的数量（可以看出，这个连通块只能是树），那么无论如何选择边的方向，总有至少一个点入度为0。

而如果存在一个连通块，块内边的数量大于点的数量，那么剩余部分点的数量大于边的数量，可以得出有至少存在一个连通块，块内点的数量大于边的数量

（充分性）可以看出，每个连通块都是一个环或基环树。

对于每个连通块，这样构造：将每个度为1的节点对应的边指向这个点，对剩余部分继续构造，这样最后只剩一个环，而这个环上只要都朝一个方向就行了

大致思路就是把叶子节点一个个撸下来，最后只剩一个环

由上面充分性的证明，处理不在环上的点时，只有唯一的一种构造方案，而处理环时，有两个方向，并且各个连通块独立。由乘法原理不难得出答案

然后就可以O(n)做了

关于出题人说的造数据难，大概就是因为没有发现这些特点吧QWQ

具体做法：

  1. 先把n=0的情况特判掉（答案为0）

  2. 建图，dfs一遍，记录每个点所属的连通块

  3. 判断每个连通块内边数是否等于点数

  4. 统计连通块数目，计算答案

其中第三步我是这样做的：计算连通块内点的度数之和，如果不满足度数之和是点个数之和的二倍，则答案为0。这应该很显然吧QWQ

最后放代码：

注：这里默认对998244353取模了，对于这个题的数据没问题

#include<cstdio>
long long read(){
    long long n=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){n=n*10+c-'0';c=getchar();}
    return n;
}
const int N=300007;
#define next next2
int head[N],next[N*2],ver[N*2],tot;
int gid[N];
int deg[N];
int cnt[N],cdeg[N];
void add(int a,int b){
    deg[a]++;
    deg[b]++;
    tot++;
    ver[tot]=b;
    next[tot]=head[a];
    head[a]=tot;
    tot++;
    ver[tot]=a;
    next[tot]=head[b];
    head[b]=tot;
}

void dfs(int id,int p){
    gid[id]=p;
    for(int i=head[id];i;i=next[i]){
        if(gid[ver[i]])continue;
        dfs(ver[i],p); 
    }
}
int n,a,b;
long long ans=1;
int main(){
    n=read();
    if(n==0){
        printf("0\n");
        return 0;
    }
    for(int i=1;i<=n;i++){//建图
        a=read();
        b=read();
        add(a,b);
    }
    for(int i=1;i<=n;i++){//DFS求每个点所属的连通块编号
        if(!gid[i])dfs(i,i);
    }
    for(int i=1;i<=n;i++){//统计每个连通块内的信息
        cnt[gid[i]]++;
        cdeg[gid[i]]+=deg[i];
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]*2!=cdeg[i]){//判断不合法情况
            printf("0\n");
            return 0;
        }
        if(cnt[i]!=0)ans=ans*2%998244353;//计算答案
        //注：这里cnt[i]=0表示这个编号没有被使用，也就是不算一个连通块
    }
    printf("%lld\n",ans);
}