12544 - Beehives

[brianfry713]

Use this thread to discuss this problem.

[Zyaad Jaunnoo]

I am using "normal" dfs for this problem. I number each node and when I hit an already visited node, I get the number of nodes in the cycle by the difference of their ids + 1. But WA

Any catch? Below is my code. Thanks for your help.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

const int MaxN  = 555;
const int White = 0;
const int Gray  = 1;
const int Black = 2;

int T, n, m;
vector<int> g[MaxN];
int color[MaxN], id[MaxN], parent[MaxN];

void Init() {
  for (int i = 0; i < MaxN; i++) {
    color[i] = White;
    id[i] = 0;
    g[i].clear();
  }
}

void Input() {
  Init();
  scanf("%d %d", &n, &m);
  
  int u, v;
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
}

int dfs(int u, int tag) {
  int r = 999;
  
  color[u] = Gray;
  id[u] = tag;
  for (auto v : g[u]) {
    if (v == parent[u]) continue;
    
    if (color[v] == Gray) {
      r = min(r, id[u] - id[v] + 1);
    }
    else if (color[v] == White) {
      parent[v] = u;
      r = min(r, dfs(v, tag+1));
    }
  }
  
  color[u] = Black;
  return r;
}

void Solve(int t) {
  int minNodes = 999;
  
  for (int i = 0; i < n; i++) {
    if (color[i] == White) {
      minNodes = min(minNodes, dfs(i, 1));
    }
  }
  
  if (minNodes == 999)
    printf("Case %d: impossible\n", t);
  else
    printf("Case %d: %d\n", t, minNodes);
}

int main() {
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    Input();
    Solve(t);
  }
  
  return 0;
}