具体题目如图:
代码如下:
//算法求解:先写出判断是否是连通图的方法,然后用for循环判断一下即可
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define N 100
int Tree[N];
int sum[N],max;//记录连通分量中个数
vector<int> E[N];//存储以数组下标为一个终点的边的信息,重点*************************
int findRoot(int x){//并查集思想,查找一个结点的根节点
if(Tree[x]==-1)return x;//如果已经是根节点,则返回根节点
else{
int temp=findRoot(Tree[x]);
Tree[x]=temp;
return temp;
}
}
FILE *fp1,*fp2;
int n;//代表总的顶点数
bool judge(int x){//判断去除x点后的结点是否是连通图
int i=1;
while(i<=n){
if(i!=x){//先排除以i为起点的
for(int h=0;h<E[i].size();h++){
if(E[i][h]!=x){//*************************再排除尾结点为x的结点,重点
int a=findRoot(i);
int b=findRoot(E[i][h]);
if(a!=b)
{Tree[b]=a;//将两个集合合并
sum[a]+=sum[b];//以a为根节点的连通分量个数加一
}
}
}
}
i++;
}
int j=1;
while(j<=n){//查找连通分量个数是否等于总结点数
if(j!=x){
if(Tree[j]==-1&&sum[j]==n-1)return true;//只有一个根节点则为真
if(Tree[j]==-1&&sum[j]<n-1)return false;//没有构成连通图则为假
}
j++;//上述没找到则继续下一个找
}
}
int main(){
fp1=fopen("1.in","r");
fp2=fopen("1.out","w");
fscanf(fp1,"%d",&n);
int a,b;
while(!feof(fp1)){
fscanf(fp1,"%d%d",&a,&b);
E[a].push_back(b);
}
bool flag=true;
int x;
for( x=1;x<=n;x++){
for(int h=1;h<=n;h++){//初始化为独立的根节点
Tree[h]=-1;
sum[h]=1;
}
flag=judge(x);
if(flag==false){
printf("存在这样的顶点%d\n",x);
break;
}
}
if(flag)printf("不存在这样的顶点使图中删去任何一个顶点后变得不连通。\n");
return 0;
}