洛谷 P3043 [USACO12JAN] Bovine Alliance G

题目链接

https://www.luogu.com.cn/problem/P3043

题意

给你$n$个点和$m$条无向边，现在要求你把每一条无向边都变成有向边，且每个点的出度最大为$1$，求方案数，答案对$1e9+7$取模。

思路

很容易想到，每一个连通块之间是互不影响的。因此我们可以先计算出每一个连通块的贡献，最后运用乘法原理，将所有连通块的贡献相乘。

首先，我们先考虑有一个环的联通块。

如上图所示，当连通块中有一个环的时候，只有两种方案。

考虑没有环的连通块：

如上图所示，在无环的连通块中，一定存在一个点的出度是$0$，其余点的出度是$1$的方案，因此贡献为$n$。

对于边数大于点数的连通块，一定没有符合要求的情况，贡献为$0$。

因此，我们只需要用DFS统计出每一个连通块中的点数和边数即可。

无向图中的边数 = （入度 + 出度）/ $4$。

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

typedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;

const int N = 1e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

std::mt19937 rnd(time(0));

int n, m, node, edge;
bool st[N];
int indu[N], outdu[N];
vector<int>mp[N];
void dfs(int u)
{
    node++;
    edge += (indu[u] + outdu[u]);
    st[u] = true;
    for (int j : mp[u])
    {
        if (st[j]) continue;
        dfs(j);
    }
}
void solve(int test_case)
{
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        mp[u].push_back(v);
        mp[v].push_back(u);
        indu[u]++, indu[v]++, outdu[u]++, outdu[v]++;
    }
    int ans = 1;
    for (int i = 1; i <= n; i++)
    {
        if (!st[i])
        {
            node = edge = 0;
            dfs(i);
            edge /= 4;
            if (node > edge)
            {
                ans = ans * node % mod;
                continue;
            }
            if (node == edge)
            {
                ans = ans * 2 % mod;
                continue;
            }
            cout << 0 << endl;
            return;
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve(i);
    }
    return 0;
}