2019 China Collegiate Programming Contest Qinhuangdao Onsite

左手的ㄟ右手 2021-07-16 13:45 242阅读 0赞

F. Forest Program（图论、环的求取）

思路：如果没有环的话，每个元素都没有限制，总贡献2^n。但条件是必须使剩下的图全是树，也就是说环必须去掉。那么直接dfs深度优先搜索，看有多少个环，用deep记录长度。每遍历到一个环就把乘上这个环的贡献 pow(2,环的长度)-1（这个环只有所有边全取的情况不行）。

Code:

#include<iostream>
    #include<string>
    #include<stdio.h>
    #include<map>
    #include<memory.h>
    #include<vector>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    typedef long long ll;
    using namespace std;
    const int Max = 4e6 + 5;
    int u[Max], v[Max], nex[Max];
    int first[Max], k = 0;
    map<int, int> ma;
    ll ans = 1, sum = 0;
    const int Mod = 998244353;
    
    ll qpow(ll a, ll b) { 
    	ll ans = 1, base = a;
    	while (b) { 
    		if (b & 1) ans = ans * base % Mod;
    		base = base * base % Mod;
    		b >>= 1;
    	}
    	return ans;
    }
    
    void add(int a, int b)
    { 
    	u[++k] = a;
    	v[k] = b;
    	nex[k] = first[a];
    	first[a] = k;
    }
    
    void dfs(int n, int pre, int deep)
    { 
    	ma[n] = deep;
    	for (int k = first[n]; k != -1;k = nex[k])
    	{ 
    		if (v[k] == pre)continue;
    		if (ma[v[k]]==1e9)continue;
    		if(ma[v[k]]==0) dfs(v[k], n, deep + 1);
    		else if (ma[v[k]] > 0)
    		{ 
    			ans = ans * (qpow(2, deep - ma[v[k]]+1) - 1) % Mod;
    			sum += deep - ma[v[k]] + 1;
    		}
    	}
    	ma[n] = 1e9;
    }
    
    int main()
    { 
    	FAST;
    	int n, m;cin >> n >> m;
    	memset(first, -1, sizeof(first));
    	for (int i = 1;i <= m;i++)
    	{ 
    		int u, v;cin >> u >> v ;
    		add(u, v), add(v, u);
    	}
    	for (int i = 1;i <= n;i++)if (ma[i] == 0)dfs(i,-1,1);
    	cout << qpow(2, m - sum) * ans % Mod << endl;
    
    }