题意，一个无向图，求该无向图中不小于3节点的最小奇数环。
思路bfs，但因为要求环上点的数目为奇数，所以不能简单的用一个vis数组记录点是否已访问过，可以改成二维的，
vis[u][0]表示点在偶数环中出现过,vis[u][1]表示点在奇数环中出现过
?
#include #include #include #include #include #include #include #include #include #include #include #include #include #define eps 1e-6 #define LL long long using namespace std; const int maxn = 1000 + 10; const int INF = 0x3f3f3f3f; int n, m, kase; int vis[maxn][2], dis[maxn]; vector G[maxn]; void init() { for(int i = 1; i <= n; i++) G[i].clear(); cin >> n >> m; int u, v; for(int i = 0; i < m; i++) { cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } } int bfs(int u) { memset(vis, 0, sizeof(vis)); queue q; q.push(u); dis[u] = 1; vis[u][1] = 1; while(!q.empty()) { int v = q.front(); q.pop(); for(int i = G[v].size() - 1; i >= 0; i--) { int tmp = G[v][i]; dis[tmp] = dis[v] + 1; if(tmp == u && dis[v] >= 3 && dis[v]%2 == 1) return dis[v]; if(vis[tmp][dis[tmp]%2]) continue; vis[tmp][dis[tmp]%2] = 1; q.push(G[v][i]); } } return INF; } void solve() { int ans = INF; for(int i = 1; i <= n; i++) ans = min(ans, bfs(i)); if(ans != INF) printf("Case %d: JYY has to use %d balls.\n", ++kase, ans); else printf("Case %d: Poor JYY.\n", ++kase); } int main() { //freopen("input.txt", "r", stdin); int t; cin >> t; while(t--) { init(); solve(); } return 0; }