CSES - HIIT Open 2019 - Results
Submission details
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
...