hdu 6736 dfs

题目链接：hdu6736

这个题目由于题目对于给的图有很严重的限制，就是每个边最多只能处于一个简单的循环中，那么其实对于所有的图，都会是那种有一条链，链上的节点有个简单环，简单环的节点又有一条链如此反复。
通过分析其实就可以知道，对于每一个边数为n的环，让他变成树的方案数目是2^n -1;就是拆一条的方案+拆2条+。。。。+拆n条。
对于每一条单独的链，让他变成树的方案数是2^n ，因为链的话可以不用拆也是一种情况。那么答案就是乘上所有的环的方案数目在乘上所有链的方案数目。由于链的方案数最后是乘法所以你所有链的方案数就是所有链的边数的总和为n，链能给出的答案也是 2^n ; 也就是我们只要算出所有环的边数-去总边数得到的剩余边数就是所有链的边数，直接算答案就可以，不需要对于每一条链分别算答案。
接下来就是，如何求每一个环的边数，我采取的就是去记录下每个点的深度（像树那样），根的深度为1，因为这个图限制这么大才可以这么去求，当我发现一个节点（深度为d1）的一条边指向了我一个走过的点(深度为d2)，那么我就发现了一个环，环的边数就是d2-d1+1;

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
#define ll long long
using namespace std;
const int max_ = 1000000 + 50;
const ll p = 998244353;
inline int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
ll binaryPow(ll a, ll b, ll m) {
	ll ans = 1;
	while (b > 0) {
		if (b & 1) {
			ans =  ((ans%m)* (a % m))%m;
		}
		a =( (a%m) *(a % m))%m  ;
		b >>= 1;
	}
	return ans%m;
}
int head[max_], xiann = 2,n,m, deep[max_];
struct {
	int next, to,pan;
}xian[max_];
void add_(int a, int b) {
	xian[xiann].next = head[a];
	xian[xiann].to = b;
	xian[xiann].pan = 0;
	head[a] = xiann;
	xiann++;
}
int vis[max_], ans =1, num = 0;
stack<int> sta;
void dfs(int now, int fa, int dep) {
	vis[now] = 1;
	deep[now] = dep;
	for (int i = head[now]; i; i = xian[i].next) {
		if (xian[i].pan)continue;
		int to = xian[i].to;
		xian[i].pan = 1; xian[i ^ 1].pan = 1;
		if (vis[to]) {
			int t = deep[now] - deep[to] + 1;
			num += t;
			ans = ((ans%p)*((binaryPow(2, t, p) - 1) % p)) % p;
			ans %= p;
			continue;
		}
		dfs(to , now,dep+1);
	}
}

int main() {
	while (cin >> n >> m) {
		for (int i = 1; i <= m; i++) {
			int a = read(), b = read();
			add_(a, b); add_(b, a);
		}
		dfs(1, -1, 1);
		int t = m-num;
		ans = ((ans%p)*(binaryPow(2, t, p) % p)) % p;
		ans %= p;
		cout << ans<<endl;
		xiann = 2;
		for (int i = 0; i <= n + 1; i++) {
			deep[i] = head[i] = vis[i] = 0;
		}
		ans = 1; num = 0;
	}
	return 0;
}