简答题
偏难
#12861
简单路径 题目描述 给定一个简单无向图,包含 N 个顶点和 M 条边。顶点编号为 1 至 N。每个顶点的度数不超过 10。 定义一条简单路径为顶点序列 v 1…
简单路径
题目描述
给定一个简单无向图,包含 N 个顶点和 M 条边。顶点编号为 1 至 N。每个顶点的度数不超过 10。
定义一条简单路径为顶点序列 v1,v2,…,vk,满足 v1=1,相邻顶点有边相连,且所有顶点互不相同(长度为 0 的路径仅包含顶点 1 本身)。
设所有这样的简单路径的总数为 K。 如果 K>2200,则输出 X;否则输出 K。
输入格式
第一行,两个整数 N,M。
接下来 M 行,每行两个整数 ui,vi,表示一条边。
输出格式
输出一个整数或大写字母 X。
输入样例#1
4 2 1 2 2 3
输出样例#1
3
输入样例#2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
输出样例#2
16
输入样例#3
8 21 2 6 1 3 5 6 3 8 3 6 4 7 4 6 3 4 1 5 2 4 1 2 2 7 1 4 3 5 2 5 2 3 4 5 3 7 6 7 5 7 2 8
输出样例#3
2023
说明提示
1≤N≤2×105
0≤M≤min(2×105, 2N(N−1))
1≤ui,vi≤N
图是简单图,每个顶点度数 ≤10
限制
时间限制:1000ms
内存限制:256MiB
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int LIMIT = 1 << 20;
const int MAXN = 200005;
vector<int> g[MAXN];
bool vis[MAXN];
int ans;
void dfs(int u)
{
ans++;
if (ans > LIMIT) return;
for (int v : g[u])
{
if (!vis[v])
{
vis[v] = true;
dfs(v);
vis[v] = false;
if (ans > LIMIT) return;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
memset(vis, 0, sizeof(vis));
ans = 0;
vis[1] = true;
dfs(1);
if (ans > LIMIT)
cout << "X\n";
else
cout << ans << "\n";
return 0;
}</pre>
这道题暂未补解析。