AtCoder Beginner Contest 226

E - Just one

题目描述：

n个点，m条边的无向图，有2^m种有向图，问有多少种有向图使的每个点只有一个出度

思路：

假设一个联通分量中有p个点，每个点有一个出度，则有p条边，所以我们计算每个联通分量的点数和边数是否相等，如果有一个不想等则ans是0，否则是2的联通分量数量次方

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
//#define mid ((l + r)>>1)
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不改范围见祖宗!
//inline int IntRead(){char ch = getchar();int 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;}

#define MAX 300000 + 10
int n, m;
int x, y, z;
int fa[MAX];
int getfa(int x){
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
inline void emerge(int x, int y){
    fa[getfa(x)] = getfa(y);
}
int bian, dian;
bool vis[MAX];
vector<int>tr[MAX];
void dfs(int u){
//    cout<<u<<" --> ";
    if(vis[u])return;
    vis[u] = 1;
    ++dian;
    bian += tr[u].size();
    for(int v : tr[u]){
        dfs(v);
    }
    return;
}
ll q_pow(ll a, ll b){
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void work()
{
    cin>>n>>m;
    ll p = 0;
    while (m--) {
        cin>>x>>y;
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[i]){
            bian = dian = 0;
            dfs(i);
//            cout<<dian<<' '<<bian<<endl;
            bian /= 2;
            if(bian != dian){
                cout<<0<<endl;
                return;
            }
            ++p;
        }
    }
    cout<<q_pow(2, p)<<endl;
}

int main(){
    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}