Regionals 2012, Europe - Southwestern A.Beehives

此題不難，但是練習賽5小時內沒有A掉.......最後還是因為沒讀清題意，多輸出了一行空行

簡化題意就是求無向圖中的最小環問題。剛開始dfs找，tle了，才發現枚舉每個點，再進行整幅圖的dfs找最優解必然跪。

寫bfs就好多了，枚舉每個點，當廣搜時碰到已經訪問過的點並且不是它的前驅結點，此時就成環了。但不能退出廣搜，必須繼續搜索與之比較大小。

因為最先找到的環不一定是最小的環，同一層次上的點還是有先後搜索順序的。

#include <iostream>  
#include <cstdio>  
#include <vector>  
#include <cstring>  
#include <queue>  
# define INF 0x7FFFFFFF  
using namespace std; 
int n,m; 
int minn; 
struct node { 
    int u,f; 
}; 
int sum[505]; 
int tmp,ok; 
vector<int> v[505]; 
 
void init() { 
    for(int i=0; i<=n; i++) { 
        v[i].clear(); 
    } 
    memset(sum,-1,sizeof(sum)); 
} 
 
void bfs(int u0) { 
    queue<node> q; 
    node t; 
    t.f = -1; 
    t.u = u0; 
    sum[u0] = 0; 
    q.push(t); 
    while(! q.empty()) { 
        t = q.front(); 
        node tt; 
        q.pop(); 
        int size = v[t.u].size(); 
        for(int i=0; i<size; i++) { 
            tt.f = t.u; 
            tt.u = v[t.u][i]; 
            if(tt.u == t.f) 
                continue; 
            if(sum[tt.u] == -1) { 
                q.push(tt); 
                sum[tt.u] = sum[t.u] + 1; 
            } else if(sum[tt.u] + sum[t.u] > 1 ) { 
                int tmp = sum[tt.u] + sum[t.u] + 1; 
                if(minn > tmp) minn = tmp; 
            } 
        } 
    } 
} 
 
int main() { 
    int t,i,j,a,b; 
    cin >> t; 
    int casee = 1; 
    while(t --) { 
        scanf("%d%d",&n,&m); 
        init(); 
        for(i=0; i<m; i++) { 
            scanf("%d%d",&a,&b); 
            v[a].push_back(b); 
            v[b].push_back(a); 
        } 
        printf("Case %d: ",casee++); 
        minn = INF; 
        for(i=0; i<n; i++) { 
            memset(sum,-1,sizeof(sum)); 
            //ok = 0;  
            bfs(i); 
        } 
        if(minn == INF) cout << "impossible" << endl; 
        else cout << minn << endl; 
    } 
    return 0; 
}