NOIP训练营内部训练题！

◆ ◆ ◆

解析在代码后,记得先思考哦

#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];

queueq;

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;="">

    cout<>

    return 0;

}

将每个联通块的贡献乘起来就是答案

如果一个联通块的边数>点数 ，那么无解

如果边数=点数，那么贡献是 2

如果边数=点数-1,那么贡献是点数