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

Code

#include <bits/stdc++.h>
using namespace std;
int t;
int n, m;
vector<int> rt[101];
int u[101];
int f(int c, int p){
if (u[c]){
++u[c];
return 1;
}
u[c]=1;
int cc=0;
for (auto w:rt[c]){
if (w==p) continue;
int a=f(w, c);
if (a==-1) return -1;
cc+=a;
}
if (cc>2) return -1;
cc-=2*(u[c]-1);
return cc;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> t;
for (int ii=0;ii<t;++ii){
cin >> n >> m;
for (int i=1;i<=n;++i) rt[i].clear();
for (int i=1;i<=n;++i) u[i]=0;
for (int i=0;i<m;++i){
int a, b;
cin >> a >> b;
rt[a].push_back(b);
rt[b].push_back(a);
}
bool h=0;
for (int i=1;i<=n;++i){
if (!u[i]) {
int w=f(i,i);
if (w==-1) h=1;
}
}
cout << (h?"YES\n":"NO\n");
}
}

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
...