CSES - HIIT Open 2019 - Results
Submission details
Task:Many Cycles
Sender:bigint bugaa
Submission time:2019-05-25 12:32:05 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.02 sdetails

Code

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
using ll = long long;
const int INF = 1e9 + 7;

// 4 5
// 1 2
// 1 3
// 1 4
// 2 3
// 3 4

const int N = 1e5;
vector<pair<int, int>> conns[N];
int ind[N];

int dfs(int i, int pe, int ci) {
	// cerr << "dfs to " << i << ' ' << pe << ' ' << ci << '\n';
	int res = INF;
	ind[i] = ci;
	++ci;

	for (auto pr : conns[i]) {
		if (pr.second == pe) continue;
		int t = pr.first;

		// cerr << t << ' ' << ind[t] << '\n';
		int sub = INF;
		if (ind[t] != INF) {
			sub = ind[t];
		} else {
			// cerr << " call with " << t << ' ' << pr.second << ' ' << ci << '\n';
			sub = dfs(t, pr.second, ci);
		}
		if (sub == -2) return -2;
		if (sub != INF && sub <= ind[i]) {
			if (res != INF) return -2;
			res = sub;
		}
	}
	// cerr << i << ' ' << pe << ' ' << ci << ": " << res << '\n';
	return (res < ind[i] ? res : INF);
}

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		conns[i].clear();
		ind[i] = INF;
	}
	for (int j = 0; j < m; ++j) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		conns[a].push_back({b, j});
		conns[b].push_back({a, j});
	}

	bool fail = false;
	for (int i = 0; i < n; ++i) {
		if (ind[i] == INF) {
			int sub = dfs(i, -1, 0);
			if (sub == -2) fail = true;
		}
	}
	if (fail) cout << "YES\n";
	else cout << "NO\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	for (int ti = 0; ti < t; ++ti) solve();
}

Test details

Test 1

Verdict: ACCEPTED

input
1000
100 78
97 68
75 90
58 80
...

correct output
YES
YES
YES
YES
NO
...

user output
YES
YES
YES
YES
NO
...
Truncated

Test 2

Verdict: ACCEPTED

input
11
2 1
1 2
6 6
1 2
...

correct output
NO
NO
NO
YES
YES
...

user output
NO
NO
NO
YES
YES
...