蓝桥杯2013年第四届真题-危险系数 BFS判断连通

解题思路:
    每次删掉一个点，BFS判断连通，如果不连通则cnt++

注意事项:

参考代码:

#include <iostream>
#include <queue>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
using namespace std;
typedef long long LL;
int n,m,vis[1111],cnt=0,a,b,s,o;
vector<int> G[1111];
int main() {
    ios::sync_with_stdio(0);
    cin>>n>>m;
    _for(i,0,m){
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    cin>>s>>o;
    _for(del,1,m+1)if(del!=s&&del!=o){
        mset(vis,0,1111);
        vis[del]=1;
        //
        queue<int> q;
        int ok=0;
        q.push(s);vis[s]=1;
        while(!q.empty()){
            int v=q.front();q.pop();
            vis[v]=1;
            if(v==o){ok=1;break;}
            int len=G[v].size();
            _for(i,0,len)if(!vis[G[v][i]]){
                vis[G[v][i]]=1;
                q.push(G[v][i]);
            }
        }
        if(!ok)cnt++;
    }
    cout<<cnt;
}