首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#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 &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cstring&gt; using namespace std; const int LIMIT = 1 &lt;&lt; 20; const int MAXN = 200005; vector&lt;int&gt; g[MAXN]; bool vis[MAXN]; int ans; void dfs(int u) {     ans++;     if (ans &gt; LIMIT) return;     for (int v : g[u])     {         if (!vis[v])         {             vis[v] = true;             dfs(v);             vis[v] = false;             if (ans &gt; LIMIT) return;         }     } } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     int n, m;     cin &gt;&gt; n &gt;&gt; m;     for (int i = 0; i &lt; m; ++i)     {         int u, v;         cin &gt;&gt; u &gt;&gt; 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 &gt; LIMIT)         cout &lt;&lt; "X\n";     else         cout &lt;&lt; ans &lt;&lt; "\n";     return 0; }</pre>
这道题暂未补解析。