CSES - HIIT Open 2019 - Results
Submission details
Task:Many Cycles
Sender:O(n^10)
Submission time:2019-05-25 13:00:19 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.04 sdetails
#2ACCEPTED0.02 sdetails

Compiler report

input/code.cpp: In function 'bool dfs(int, int)':
input/code.cpp:17:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < adj[x].size(); i++) {
                   ~~^~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>

using namespace std;
int t;
vector<int> adj[102];

int vis[103], cycles[103];


int vid = 1;
int arr[104][104];
int par[104];

bool dfs(int x, int p) {
  vis[x] = vid;
  //cout<<x<<" "<<p<<"\n";
  for (int i = 0; i < adj[x].size(); i++) {
    int u = adj[x][i];
    if (u == p) continue;
    if (arr[x][u] == vid) continue;
    
    if (vis[u] == vid) {
      //cout<<x<<" on syklissä ja "<<u<<" on syklissä\n";
      int kk = x;
      while (kk != u) {
        cycles[kk]++;
        //cout<<"cycles["<<kk<<"] ++ = "<<cycles[kk]<<"\n";
        if (cycles[kk] > 1) return true;
        kk = par[kk];
      }
      cycles[u]++;
      
      if (cycles[u] > 1) return true;
      
      arr[x][u] = vid;
      arr[u][x] = vid;
      //cout<<x<<" on syklissä ja "<<u<<" on syklissä\n";
      continue;
    }
    
    vis[u] = vid;
    par[u] = x;
    if (dfs(u, x)) return true;
  }
  
  return false;
}

bool solve(int n, int m) {
  for (int i = 0; i < m; i++) {
    int a,b; cin>>a>>b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  
  vid++;
  par[1] = 1;
  return dfs(1, 1);
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin>>t;
  for (int j = 0; j < t; j++) {
    int n, m; cin>>n>>m;
    for (int i = 1; i <= 100; i++) adj[i].clear(), cycles[i] = 0, par[i] = 0;
    
    bool res = solve(n, m);
    if (res) cout<<"YES\n";
    else cout<<"NO\n";
  }
}

Test details

Test 1

Verdict:

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

correct output
YES
YES
YES
YES
NO
...

user output
YES
NO
NO
NO
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
...