12544 - Beehives
Moderator: Board moderators
-
- 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.

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