Submission #65438902

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<array>
#include<unordered_set>
#include<unordered_map>
#include<cstring>
#include<string>
#include<memory>
#include<iomanip>
#include<cassert>
#include<cmath>
#include<random>
#include<algorithm>
#include<chrono>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define int long long
#define ld long double
#define endl '\n'

using namespace std;

constexpr int N = 200'000;
vector<int> g[N];

int timer, tin[N], tout[N], parent[N];
int s = -1, t = -1;

void dfs(int u, int p) {
	tin[u] = ++timer;
	parent[u] = p;

	for (int v : g[u]) {
		if (v == p) continue;

		if (tin[v] == 0) {
			dfs(v, u);
		}
		else if (tout[v] == 0) {
			s = v, t = u;
		}
	}
	tout[u] = ++timer;
}




void solve() {
	int n, m; cin >> n >> m;

	for (int i = 0; i < n; i++) {
		g[i].clear();
	}

	for (int i = 0; i < m; i++) {
		int u, v; cin >> u >> v; u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	if (n != m) {
		cout << "No" << endl;
		return;
	}

	dfs(0, -1);

	if (s == -1) {
		cout << "No" << endl;
		return;
	}

	int cur = t, cnt = 1;
	while (cur != s) {
		cnt++, cur = parent[cur];
	}

	cout << (cnt == n ? "Yes" : "No") << endl;
}

signed main() {
	// freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	// int q; cin >> q; while (q--)
	solve();
}

Submission Info

Judge Result