12544 - Beehives

All about problems in Volume 125. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

12544 - Beehives

Post by brianfry713 » Tue Sep 09, 2014 5:57 am

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

User avatar
Zyaad Jaunnoo
Experienced poster
Posts: 120
Joined: Tue Apr 16, 2002 10:07 am

Re: 12544 - Beehives

Post by Zyaad Jaunnoo » Tue Sep 13, 2016 10:42 pm

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;
}

Post Reply

Return to “Volume 125 (12500-12599)”

Who is online

Users browsing this forum: No registered users and 1 guest