## 12544 - Beehives

Moderator: Board moderators

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

### 12544 - Beehives

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

Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

### Re: 12544 - Beehives

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