#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("");
}
/**************************************************************
Problem: 2163
User: admin
Language: C++
Result: Accepted
Time:12 ms
Memory:1148 kb
****************************************************************/