题目描述
样例
输入
4 2
1 2
2 3
输出
3
输入
4 6
1 2
1 3
1 4
2 3
2 4
3 4
输出
16
输入
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
输出
2023
算法
dfs搜索,超过1e6的时候跳出,由于是递归不能使用return结束。要使用exit(0);
参考代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define int long long
#define x first
#define y second
#define cmp [&](PII a, PII b){ return a.y < b.y; }
const int N = 5e5+10, mod = 1e9+7, M = 5e7+5, K = 2e5+10, Z = 1e5+7, X = 1.5 * 1e9;
using namespace std;
typedef long long LL;
typedef priority_queue<int> PQI;
typedef priority_queue <int, vector<int>, greater<>> PQGI;
typedef pair<int, int> PII;
vector<vector<int>> adj(K);
vector<int> vis(K);
int ans;
int df = 0;
void dfs(int df, int x)
{
if(vis[x]) return;
ans ++;
if(ans == 1000000)
{
cout << ans << endl;
exit(0);
}
vis[x] = 1;
for(auto y : adj[x])
{
dfs(df, y);
}
vis[x] = 0;
}
void solve()
{
int n, m; cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// auto dfs = [&](auto dfs, int x)
// {
// if(vis[x]) return;
// ans ++;
// if(ans == 1000000)
// {
// cout << ans << endl;
// exit(0);
// }
// vis[x] = 1;
// for(auto y : adj[x])
// {
// dfs(dfs, y);
// }
// vis[x] = 0;
// };
dfs(df, 1);
cout << ans << endl;
}
signed main()
{
IOS; int T = 1;
cin.tie(nullptr);
cout.tie(nullptr);
// cin >> T;
while( T -- ) solve();
return 0;
}