试题 历届试题 危险系数(c++)

思路：暴力枚举
注意这是无向图， 像我的代码里面，一条边要存两次

#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;
//最大边数
const int maxe(2e3 + 5);
//最大点数
const int maxn(1e3 + 5);
//边结构定义
typedef struct Edge{
    int from, to;
    //默认是不被破坏
    bool destroy;
    Edge(int _from = -1, int _to = -1):from(_from), to(_to), destroy(false) {};
}Edge;

Edge es[maxe];
bool vis[maxn];
int n, m, st, en, ans;
bool BFS(int st, int en)
{
    queue<int> QNode;
    QNode.push(st);
    while(!QNode.empty())
    {
        int cur_node = QNode.front();
        QNode.pop();
        //cout << '[' << cur_node << ']' << endl;
        vis[cur_node] = true;
        for (int i = 1; i <= 2 * m; i++)
        {
            if (es[i].from == cur_node && vis[es[i].to] == false && es[i].destroy == false)
            {
                //cout << "[" << es[i].from << ", " << es[i].to << "]" << endl;
                if (es[i].to == en)
                    return true;
                QNode.push(es[i].to);
                vis[es[i].to] = true;
            }
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    memset(vis, false, sizeof(vis));
    cin >> n >> m;
    for (int i = 1; i <= 2 * m; i+=2)
    {
        int from, to;
        cin >> from >> to;
        es[i].from = from;
        es[i].to = to;
        es[i].destroy = false;
        es[i + 1].from = to;
        es[i + 1].to = from;
        es[i + 1].destroy = false;
    }
    cin >> st >> en;
    if (BFS(st, en) == false) cout << -1 << endl;
    else 
    {
        ans = 0;
        for (int i = 1; i <= n; i++)
        {
            //关键点不能是 st & en
            if (i != st && i != en)
            {
                for (int j = 1; j <= 2 * m; j++)
                {
                    if (es[j].from == i || es[j].to == i)
                        es[j].destroy = true;
                }
                //vis每次都要清空（初始化）
                memset(vis, false, sizeof(vis));
                if (BFS(st, en) == false) ans++;
                //边用完了要返回到初始状态
                for (int j = 1; j <= 2 * m; j++)
                    es[j].destroy = false;
            }
        }
        cout << ans << endl;
    }
    system("pause");
    return 0;
}

本文地址：https://blog.csdn.net/qq_45591813/article/details/108974115