蓝桥杯2013年第四届真题-危险系数 （C++代码）

解题思路:

注意事项:

参考代码:

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector<int> V[1005];
int n, m;
bool vis[1005];
int num[1005];
int path;
int way[1005];

void dfs(int u, int v, int id) {
	vis[u] = true;
	way[id] = u;
	if (u == v) {
		path++;
		for (int i = 0; i <= id; i++) {
			num[way[i]]++;
		}
		return;
	}
	for (int i = 0; i < V[u].size(); i++) {
		if (vis[V[u][i]])
			continue;
		dfs(V[u][i], v, id + 1);
		vis[V[u][i]] = false;
	}
}

int main() {

	while (cin >> n >> m) {
		for (int i = 0; i < 1005; i++) {
			V[i].clear();
			vis[i] = false;
			num[i] = 0;
			way[i] = 0;
		}
		path = 0;
		int u, v;
		for (int i = 1; i <= m; i++) {
			cin >> u >> v;
			V[u].push_back(v);
			V[v].push_back(u);
		}
		cin >> u >> v;

		int res = 0;
		dfs(u, v, 0);
		for (int i = 1; i <= n; i++) {
			if (num[i] == path) {
				res++;
			}
		}
		if (path) {
			cout << res - 2 << endl;
		}
		else {
			cout << -1 << endl;
		}
	}

	return 0;
}