fly

用户名：CNetName

访问量：2074

签　名：

等　　级
排　　名	31019
经　　验	493
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	湖南师范大学
专　　业

　　自我简介：

TA的其他文章

公交汽车-题解(C++代码)
浏览：502

蓝桥杯2013年第四届真题-危险系数（C++代码）
浏览：149

你可能喜欢

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

蓝桥杯2013年第四届真题-危险系数（C++代码）

　　作者: fly　　　　发表时间：2020-02-15 23:06:58 浏览：149　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-危险系数

两种方法（水平有限，看客自行参考）
#### 方法1
dfs用于判断两点在删除某点后是否依然联通，每次删除后都判断一次，由于遍历次数较多，采用了记忆深搜，降低了时间开销，但增大了空间开销
```cpp
#include<iostream>
#include<vector>
#include<list>
using  namespace std ;

vector<list<int>> vex;    //图，邻接表结构
vector<bool> visited;     //记录遍历过的点
vector<vector<vector<short int>>> ms;   //记忆搜索
bool dfs(int u,int v,int x){    //深搜，删除点x后，从u到v是否连通
    if(ms[u][v][x]!=-1) return ms[u][v][x];
    if(u==v)  return ms[u][v][x]=1;
    visited[u]=true;
    for(list<int>::iterator it=vex[u].begin();it!=vex[u].end();it++){
        if(*it==x) continue;
        if(!visited[*it])
            if(dfs(*it,v,x)) return ms[*it][v][x]=1;
    }
    return ms[u][v][x]=0;
}

int main(){
     int n,m;
     cin>>n>>m;
     vex.resize(n+1);
     int u,v;
     for(int i=1;i<=m;i++){
        cin>>u>>v;
        vex[u].push_back(v);
        vex[v].push_back(u);
     }
     cin>>u>>v;        //以上为输入部分

int sum=0;   //关键点数
     ms.resize(n+1);
     for(int i=1;i<=n;i++) ms[i].resize(n+1);
     for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        ms[i][j].assign(n,-1);     //初始化ms，-1表示未深搜的状态
     visited.assign(n,0);    //初始化visited为0
     if(!dfs(u,v,0)){    //如果不通，直接输出-1
        cout<<-1;
        return 0;
     }
     for(int i=1;i<=n;i++){      //逐个点删除后看是否依然连通
        if(i==u||i==v)  continue;
        visited.assign(n,0);
        if(!dfs(u,v,i))  sum++;
     }
     cout<<sum;
     return 0;
 }

```

#### 方法2 
在之前的基础上修改。DFS用于遍历两点的所有路径。不用多次遍历。
统计每条可以连通两点的路径，把每条路径上的点的标记加1，最后点的标记数等于路径数的即为关键点。

```cpp
#include<iostream>
#include<vector>
#include<list>
#include<stack>
using  namespace std ;

vector<list<int>> vex;
vector<bool> visited;
vector<vector<vector<short int>>> ms;
stack<int> path;
vector<int> pointNumInPath;  //点的标记，代表参与的路径数
int pathNum=0,keyPointNum=0;   //路径数，关键点数

bool dfs(int u,int v,int x){
    if(ms[u][v][x]!=-1) return ms[u][v][x];
    if(u==v)  return ms[u][v][x]=1;
    visited[u]=true;
    for(list<int>::iterator it=vex[u].begin();it!=vex[u].end();it++){
        if(*it==x) continue;
        if(!visited[*it])
            if(dfs(*it,v,x)) return ms[*it][v][x]=1;
    }
    return ms[u][v][x]=0;
}

void printPath(){     //打印路径
    stack<int> temp;
    int n=path.size();
    for(int i=0;i<n;i++){
        temp.push(path.top());
        path.pop();
    }
    for(int i=0;i<n;i++){
        cout<<temp.top()<<" ";
        path.push(temp.top());
        temp.pop();
    }
    cout<<endl;
}
void pointNum(){   //把路径上的点的标记加一
    stack<int> temp;
    int n=path.size();
    for(int i=0;i<n;i++){
        temp.push(path.top());
        path.pop();
    }
    for(int i=0;i<n;i++){
        pointNumInPath[temp.top()]++;
        path.push(temp.top());
        temp.pop();
    }
}
void DFS(int u,int v){    //遍历所有连通u，v两点的路径
    if(u==v){
        path.push(u);
//        printPath();
        pathNum++;
        pointNum();
        return;
    }
    path.push(u);
    visited[u]=true;
    for(list<int>::iterator it=vex[u].begin();it!=vex[u].end();it++){
        if(!visited[*it]){
            DFS(*it,v);
            path.pop();
            visited[*it]=false;
        }
    }
}

int main(){
     int n,m;
     cin>>n>>m;
     vex.resize(n+1);
     int u,v;
     for(int i=1;i<=m;i++){
        cin>>u>>v;
        vex[u].push_back(v);
        vex[v].push_back(u);
     }
     cin>>u>>v;
//     int sum=0;
//     ms.resize(n+1);
//     for(int i=1;i<=n;i++) ms[i].resize(n+1);
//     for(int i=1;i<=n;i++)
//        for(int j=1;j<=n;j++)
//        ms[i][j].assign(n,-1);
     visited.assign(n,0);
     pointNumInPath.assign(n,0);
     DFS(u,v);
     if(pathNum==0){
        cout<<-1;
        return 0;
     }
     for(int n:pointNumInPath){     //统计关键点
        if(n==pathNum) keyPointNum++;
     }
     cout<<keyPointNum-2;   //减去两个端点
//     if(!dfs(u,v,0)){
//        cout<<-1;
//        return 0;
//     }
//     for(int i=1;i<=n;i++){
//        if(i==u||i==v)  continue;
//        visited.assign(n,0);
//        if(!dfs(u,v,i))  sum++;
//     }
//     cout<<sum;
     return 0;
 }

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

fly

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

【作业调度方案】（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

蓝桥杯2013年第四届真题-危险系数（C++代码）

评论区

精彩推荐

【绝对值排序】（C++代码）

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【排队买票】（C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

fly

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

【作业调度方案】 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

蓝桥杯2013年第四届真题-危险系数 （C++代码）

评论区

精彩推荐

【绝对值排序】 （C++代码）

c primer plus 第十二章 12.1小节

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

【排队买票】 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

DNA （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

【作业调度方案】（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

蓝桥杯2013年第四届真题-危险系数（C++代码）

　　评论区

【绝对值排序】（C++代码）

【排队买票】（C语言代码）