/*39.（树、图、算法）(2).求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。*/#include <stdio.h>#define MAX_VERTEX_NUM 20#define INFINITY 10000typedef struct ArcCell{    int adj;}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct MGraph{    int vexs[MAX_VERTEX_NUM];    AdjMatrix arcs;    int vexnum, arcnum;}MGraph;//定位顶点int LocateVex(MGraph G, int v){    for(int i = 0; i < G.vexnum; i++)    {        if(G.vexs[i] == v)            return i;    }    return -1; //means error}void CreateDN(MGraph &G) //生成有向图{    printf("Input the vexnum:");    scanf("%d",&G.vexnum);    printf("Input the arcnum:");    scanf("%d", &G.arcnum);    for(int i = 0; i < G.vexnum; i++)    {        printf("Input the %d vex:", i);        scanf("%d", &G.vexs[i]);    }    for(int i = 0; i < G.vexnum; i++)        for(int j = 0; j < G.vexnum; j++)            G.arcs[i][j].adj = INFINITY;    for(int k = 0; k < G.arcnum; k++)    {        int v1, v2, w;        printf("input the arcs vex and weight:");        scanf("%d %d %d", &v1, &v2, &w);        int i = LocateVex(G, v1);        int j = LocateVex(G, v2);        G.arcs[i][j].adj = w;    }}//有向图是否强连通bool isConnected(MGraph G){    bool connected = true;    for(int i = 0; i < G.vexnum; i++)    {        bool haveConnectedIn = false;        bool haveConnectedOut = false;        for(int j = 0; j < G.vexnum; j++)        {            if(G.arcs[i][j].adj < INFINITY)                haveConnectedOut = true;            if(G.arcs[j][i].adj < INFINITY)                haveConnectedIn = true;        }        if(haveConnectedOut != true || haveConnectedIn != true)        {            connected = false;            break;        }    }    return connected;}//得到有向图G去掉一个顶点和其相邻边后的图MGraph deleteOneVex(MGraph G, int vex){    MGraph DG;    DG.vexnum = G.vexnum - 1;    int j = 0;    for(int i = 0; i < G.vexnum; i++)    {        if(i != vex)        {            DG.vexs[j++] = G.vexs[i];         }    }    DG.arcnum = 0;    for(int i = 0; i < G.vexnum; i++)        for(int j = 0; j < G.vexnum; j++)            if(i != vex && j != vex)            {                int v = (i > vex) ? i - 1 : i;                int u = (j > vex) ? j - 1 : j;                DG.arcs[v][u].adj = G.arcs[i][j].adj;                DG.arcnum++;            }    return DG;}//查找图的割void GetGutSet(MGraph G){    bool isconnect = isConnected(G);    if(isconnect == false)    {        printf("the Graph is not connected.\n");        return;    }    int n = 0;    if(G.vexnum < 1)    {        printf("no vex");    }    else if(G.vexnum == 1)    {        printf("cut is %d\n", G.vexs[0]);    }    else    {        for(int i = 0 ; i < G.vexnum; i++)        {            MGraph DG = deleteOneVex(G, i);            bool isconnect = isConnected(DG);            if(isconnect == false)            {                printf("The %d cut vex is %d\n", n, G.vexs[i]);            }        }    }}int main(){    MGraph G;    CreateDN(G);    GetGutSet(G);    return 0;}