提供一种不用 2-SAT 的思路。

我们考虑选出的 后勤组织 的集合为 $A$ ，集合 $A$ 的大小为 $m$ 。

假设图中总边数为 $S$ ，那么 $A$ 中所有点的总 度数 $sum$ 应该等于 $S+\binom{m}{2}$。

显然，$sum \le S+ \binom{m}{2}$。所以在固定 $m$ 之后，我们只用判断度数最大的 $m$ 个点是否合法即可。

如果合法，可以考虑把度数最小的点换成其他度数相等的点，假设前 $m$ 个点选了 $a$ 个最小度数的点，总共有 $b$ 个最小度数的点，则贡献上 $\binom{b}{a}$ 即可。

可以做到 $O(n \log n )$ ，但因为读入都是 $O(n^2)$ 的，所以本文只实现了 $O(n^2)$。

（主要是我太懒了）

代码中取模是因为我感觉求个 $5000!$ 不取模太鬼畜了，可以证明答案是 $O(n)$ 的，所以取模也不会影响答案。

注意特判整个图是完全图的情况

//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register int
#define fr first
#define sd second
#define pa pair<int,int>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define N 5010
const int mod=998244353;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
inline int lowbit(int x){return x&(-x);}
int n,deg[N],x;
int S,fac[N],inv[N];
inline int C(int n,int m){return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline int Z(int x){return (x>=mod?x-mod:x);}
int main()
{
	//ios::sync_with_stdio(false);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();FOR(i,1,n){deg[i]=read();int t=deg[i];while(t--){x=read();}S+=deg[i];}//没错这种做法边都不需要读入 
	S/=2;sort(deg+1,deg+n+1);reverse(deg+1,deg+n+1);
	fac[0]=1;
	FOR(i,1,n)fac[i]=1LL*fac[i-1]*i%mod;
	inv[0]=inv[1]=1;
	FOR(i,2,n)inv[i]=1LL*inv[mod%i]*(mod-mod/i)%mod;
	FOR(i,2,n)inv[i]=1LL*inv[i-1]*inv[i]%mod;
	int sum=0,ans=0;
	FOR(i,1,n)
	{
		sum+=deg[i];
		if(sum==S+i*(i-1)/2)
		{
			int a=0,b=0,pos=i;
			while(pos>=1&&deg[pos]==deg[i])a++,b++,pos--;
			pos=i+1;
			while(pos<=n&&deg[pos]==deg[i])b++,pos++;
			ans=Z(ans+C(b,a));
		}
	}
	if(deg[n]==n-1)ans=Z(ans+mod-1);//完全图 
	cout<<ans<<'\n';
	return 0;
}
//gl

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq

D41 2-SAT P3513 [POI2011] KON-Conspiracy

#include<bits/stdc++.h>
using namespace std;

const int N=5005,M=N<<1;
int head[M],idx;
struct edge{int to,ne;}e[N*N];
int dfn[M],low[M],tim,stk[M],top,scc[M],cnt;
int n,m;
int a[N],an;      //存储后勤成员与数量
int b[N],bn;      //存储同谋成员与数量
int num[N],id[N]; //存储矛盾点的数量与编号
bool know[N][N],inb[N]; //是否认识,是否在同谋组

void add(int x,int y){
  e[++idx]={y,head[x]};
  head[x]=idx;
}
void tarjan(int x){
  dfn[x]=low[x]=++tim;
  stk[++top]=x;
  for(int i=head[x];i;i=e[i].ne){
    int y=e[i].to;
    if(!dfn[y]){ //若y尚未访问
      tarjan(y);
      low[x]=min(low[x],low[y]);
    }
    else if(!scc[y]) //若y已访问且未处理
      low[x]=min(low[x],dfn[y]);
  }
  
  if(low[x]==dfn[x]){ //若x是SCC的根
    ++cnt;
    for(int y=-1;y!=x;)
      scc[y=stk[top--]]=cnt;
  }
}
int main(){
  scanf("%d",&n);
  for(int i=1,x;i<=n;i++){
    scanf("%d",&m);
    while(m--) scanf("%d",&x),know[i][x]=true;
  }
  for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++){
      if(know[i][j]) add(i+n,j),add(j+n,i);
      else add(i,j+n),add(j,i+n);
    }
  for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
  
  for(int i=1;i<=n;i++){
    if(scc[i]==scc[i+n]) puts("0"),exit(0);
    if(scc[i]<scc[i+n]) a[++an]=i; //存储后勤成员
    else b[++bn]=i,inb[i]=1;       //存储同谋成员
  }
  for(int i=1;i<=an;i++)
    for(int j=1;j<=bn;j++)
      if(know[a[i]][b[j]]) //后勤认识同谋即矛盾点
        ++num[a[i]],id[a[i]]=b[j];
  for(int i=1;i<=bn;i++)
    for(int j=1;j<=an;j++)
      if(!know[b[i]][a[j]]) //同谋不认识后勤即矛盾点
        ++num[b[i]],id[b[i]]=a[j];
  int ans=0;
  for(int i=1;i<=n;i++){
    //i有1个矛盾点且i的矛盾点无矛盾点，可以直接交换
    if(num[i]==1 && !num[id[i]]) ++ans;
    //i无矛盾点且本组超过1人，可以直接移到对面组
    if(!num[i]&&((inb[i]&&bn>1)||(!inb[i]&&an>1))) ++ans;
  }
  if(an&&bn) ++ans; //初始解
  printf("%d\n",ans);
}