A17481. 简单路径
填空题
困难
知识点
题目描述
简单路径
题目描述
给定一个简单无向图，包含 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
参考答案
#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;
}
上一题
下一题