◆ ◆ ◆
解析在代码后,记得先思考哦
#include #include #include using namespace std; const int mod=1e9+7; #define N 100001 int front[N],to[N<><> bool vis[N]; int d[N]; queue int ans=1; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } void add(int u,int v) { to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; d[v]++; } bool bfs(int s) { while(!q.empty()) q.pop(); int p=0,e=0; q.push(s); vis[s]=true; int now; while(!q.empty()) { now=q.front(); q.pop(); p++; e+=d[now]; for(int i=front[now];i;i=nxt[i]) if(!vis[to[i]]) vis[to[i]]=true,q.push(to[i]); } if(e>p) return false; if(e==p) ans=ans*2%mod; else ans=1ll*ans*p%mod; return true; } int main() { freopen('girl.in','r',stdin); freopen('girl.out','w',stdout); int n,m; read(n); read(m); int u,v; for(int i=1;i<> { read(u); read(v); add(u,v); } for(int i=1;i<> if(!vis[i]) if(!bfs(i)) { cout<0; return="" 0;="">0;> cout<> return 0; }
将每个联通块的贡献乘起来就是答案
如果一个联通块的边数>点数 ,那么无解
如果边数=点数,那么贡献是 2
如果边数=点数-1,那么贡献是点数
联系客服