1 条题解

  • 0
    @ 2024-12-24 10:06:05

    C++ :

    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OVERFLOW -1
    typedef int Status; /* 函数结果状态代码,如OK等 */
    typedef int InfoType;
    typedef int VertexType; /* 节点类型 */
    #define MAX_VERTEX_NUM 50
    typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
    typedef struct ArcNode
    {
    	int adjvex; /* 该弧所指向的顶点的位置 */
    	struct ArcNode *nextarc; /* 指向下一条弧的指针 */
    	InfoType *info; /* 网的权值指针) */
    }ArcNode; /* 表结点 */
    typedef struct
    {
    	VertexType data; /* 顶点信息 */
    	ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */
    }VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点 */
    typedef struct
    {
    	AdjList vertices;
    	int vexnum,arcnum; /* 图的当前顶点数和弧数 */
    	int kind; /* 图的种类标志 */
    }ALGraph;
    
    int cnt; /* 全局量cnt对访问计数 */
    int low[MAX_VERTEX_NUM];
    int articulcnt;
    int articul[MAX_VERTEX_NUM];
    bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
    //void(*VisitFunc)(char* v); /* 函数变量(全局量) */
    
    Status CreateGraph(ALGraph *G)
    { /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */
    	int i,j,k;
    	int temp; /* 临时变量 */
    	VertexType va,vb;
    	ArcNode *p;
    	(*G).kind = 2;
    	scanf("%d", &(*G).vexnum);
    	(*G).arcnum = 0;
    	for(i=0;i<(*G).vexnum;i++)
    	{
    		(*G).vertices[i].data=i;
    		(*G).vertices[i].firstarc=NULL;
    	}
    	for(i=0;i<(*G).vexnum;i++)/* 构造表结点链表 */
    	{
    		for(j=0;j<(*G).vexnum;j++)
    		{
    			scanf("%d",&temp);
    			if(i<j&&temp==1)
    			{
    				va=i;/* 弧尾 */
    				vb=j;/* 弧头 */
    				p=(ArcNode*)malloc(sizeof(ArcNode));
    				p->adjvex=j;
    				p->info=NULL; /* 图 */
    				p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */
    				(*G).vertices[i].firstarc=p;
    				p=(ArcNode*)malloc(sizeof(ArcNode));
    				p->adjvex=i;
    				p->info=NULL; /* 无向图 */
    				p->nextarc=(*G).vertices[j].firstarc; /* 插在表头 */
    				(*G).vertices[j].firstarc=p;
    			}
    		}
    	}
    	return OK;
    }
    
    void DFSArticul(ALGraph G,int v0)
    { /* 从第v0个顶点出发深度优先遍历图G,查找并输出关节点。算法7.11 */
    	int min,w;
    	ArcNode *p;
    	visited[v0]=min=++cnt; /* v0是第cnt个访问的顶点 */
    	for(p=G.vertices[v0].firstarc;p;p=p->nextarc) /* 对v0的每个邻接顶点检查 */
    	{
    		w=p->adjvex; /* w为v0的邻接顶点 */
    		if(visited[w]==0) /* w未曾访问,是v0的孩子 */
    		{
    			DFSArticul(G,w); /* 返回前求得low[w] */
    			if(low[w]<min)
    				min=low[w];
    			if(low[w]>=visited[v0])
    				articul[articulcnt++]=G.vertices[v0].data; /* 关节点 */
    		}
    		else if(visited[w]<min)
    			min=visited[w]; /* w已访问,w是v0在生成树上的祖先 */
    	}
    	low[v0]=min;
    }
    
    void FindArticul(ALGraph G)
    { /* 连通图G以邻接表作存储结构,查找并输出G上全部关节点。算法7.10 */
    	/* 全局量cnt对访问计数。 */
    	int i,v;
    	ArcNode *p;
    	cnt=1;
    	low[0]=visited[0]=1; /* 设定邻接表上0号顶点为生成树的根 */
    	for(i=1;i<G.vexnum;++i)
    		visited[i]=0; /* 其余顶点尚未访问 */
    	p=G.vertices[0].firstarc;
    	v=p->adjvex;
    	DFSArticul(G,v); /* 从第v顶点出发深度优先查找关节点 */
    	if(cnt<G.vexnum) /* 生成树的根有至少两棵子树 */
    	{
    		articul[articulcnt++]=G.vertices[0].data; /* 根是关节点,输出 */
    		while(p->nextarc)
    		{
    			p=p->nextarc;
    			v=p->adjvex;
    			if(visited[v]==0)
    				DFSArticul(G,v);
    		}
    	}
    }
    
    int main()
    {
    	ALGraph g;
    	articulcnt=0;
    	CreateGraph(&g);
    	FindArticul(g);
    	sort(articul,articul+articulcnt);
    	articulcnt=unique(articul,articul+articulcnt)-articul;
    	printf("%d\n",articulcnt);
    	for(int i=0;i<articulcnt;i++)
    	{
    		printf("%d ", articul[i]);
    	}
    	puts("");
    }
    
    • 1

    信息

    ID
    1890
    时间
    1000ms
    内存
    32MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者