1 条题解
-
0
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
- 上传者