题目描述
时间：2s 空间：256M
题目描述：
一个国家有 n 个城市，城市与城市之间有一些道路，总共有 m 条。
小信在城市 11 ，他想知道从城市 11 出发，有多少条不同的旅游线路，并且要求旅游线路中不能经过同一个城市两次。
可能有很多这样的旅游线路，如果超过 106106 条，你只需要告诉小信有 106106 条即可。
输入格式：
第一行包含两个整数 n, m (1≤n≤200000, 0≤m≤min(200000,n⋅(n−1)/2)。
接下来m 行，每行两个整数 ui,vi (1≤ui,vi≤n)，表示城市 u 与 城市 v 之间有一条无向道路。
保证没有重边和自环。
输出格式：
对于每组测试数据，输出一个整数表示答案。
样例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
我的代码
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=1,vis[200005];
vector<int>v[200005];
void dfs(int x,int fa){
vis[x]=1;
for(int i=0;i<v[x].size();i++){
int nx=v[x][i];
if(vis[nx]==1 || nx==fa){
continue;
}
ans++;
if(ans>=1e6){
cout<<1e6;
exit(0);
}
dfs(nx,x);
vis[nx]=0;
}
}
int main(){
cin>>n>>m;
for(int i=1,x,y;i<=m;i++){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,-1);
cout<<ans;
return 0;
}
