具体题目如图:
代码如下:
//算法求解:先写出判断是否是连通图的方法,然后用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;
}