CSES - HIIT Open 2019 - Results
 Task: Many Cycles Sender: Game of Nolife Submission time: 2019-05-25 12:29:59 +0300 Language: C++ Status: READY Result: ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.02 sdetails

### Code

```#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

struct Bridges{
vector<int> c,h;
void dfs(vector<pair<int, int>>* g, int x, int pe, int d, vector<int>& ns){
if (h[x]) return;
h[x]=d;
ns.push_back(x);
for (auto nx:g[x]){
if (nx.S!=pe){
dfs(g, nx.F, nx.S, d+1, ns);
h[x]=min(h[x], h[nx.F]);
}
}
if (h[x]==d){
while (ns.size()>0){
int t=ns.back();
c[t]=x;
ns.pop_back();
if (t==x) break;
}
}
}
Bridges(vector<pair<int, int>>* g, int n) : c(n+1), h(n+1) {
vector<int> ns;
for (int i=1;i<=n;i++){
dfs(g, i, -1, 1, ns);
}
}
};

vector<pair<int, int>> g[111];
int n;

int u[111];

int ns,es;

void dfs(int x, const Bridges& bs){
if (u[x]) return;
u[x]=1;
ns++;
for (auto nx:g[x]){
if (bs.c[nx.F]==bs.c[x]){
es++;
}
}
for (auto nx:g[x]){
if (bs.c[nx.F]==bs.c[x]){
dfs(nx.F, bs);
}
}
}

void solve(){
int m;
cin>>n>>m;
for (int i=1;i<=n;i++){
g[i].clear();
u[i]=0;
}
for (int i=0;i<m;i++){
int a,b;
cin>>a>>b;
g[a].push_back({b, i+1});
g[b].push_back({a, i+1});
}
Bridges bs(g, n);
int f=0;
for (int i=1;i<=n;i++){
if (!u[i]){
ns=0;
es=0;
dfs(i, bs);
es/=2;
if (es>ns){
f=1;
}
}
}
if (f){
cout<<"YES"<<endl;
}else {
cout<<"NO"<<endl;
}
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tcs;
cin>>tcs;
for (int tc=0;tc<tcs;tc++){
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
...