无向图的关节点

/**

Description

给出一个无向图，求出图的关节点，如果图无关节点输出None。

数据输入：

第一行是一个整数N（1<=N<=20），表示有多少个图需要计算。

以下每个图的第一行是整数M，表示此图有多少个顶点，

以后的M行表示图的连接情况。表示连接情况的每行中首先是一个整数K，

表示有此顶点有多少条边，接着有K个整数，表示此顶点和其他K个顶点相连。

数据输出：

每行输出一个例子的关节点，关节点之间用一个空格隔开。没有关节点输出None。

Sample Input

2

3

2 2 3

1 1

1 1

4

1 2

1 1

1 4

1 3

Sample Output

1

None

*/

#include<stdio.h>
#define MAX 100

int tempArray[MAX],tempArray2[MAX][MAX];

int init(int input[][MAX]);
bool isConnected(int input[][MAX],int vertexNumber);
bool isArticulationPoint(int input[][MAX],int vertexNumber,int vertex);
//void printArray(int array[][MAX],int n);

int main()
{
    /**
        cases个用例、input用来存放输入的结点跟其他结点的连接关系
        vertexNumber表示结点数目
    */
    int cases,input[MAX][MAX],vertexNumber,i;
    bool flag;

    scanf("%d",&cases);

    while(cases--)
    {
        flag = false;
        vertexNumber = init(input);
        if(isConnected(input,vertexNumber))
        {
            for(i=1; i<=vertexNumber; i++)
            {
                if(!isArticulationPoint(input,vertexNumber,i))
                {
                    if(!flag)
                    {
                        printf("%d",i);
                        flag = true;
                    }
                    else
                    {
                        printf(" %d",i); //以后的输出多一个空格
                    }
                }
            }
        }

        if(!flag)
        {
            printf("None");
        }

        printf("\n");
    }
    return 0;
}

int init(int input[][MAX])
{
    int vertexNumber,i,j,k,temp;
    scanf("%d",&vertexNumber);

    for(i=1; i<=vertexNumber; i++)
    {
        for(j=1; j<=vertexNumber; j++)
        {
            input[i][j] = 0;
        }
    }

    for(i=1; i<=vertexNumber; i++)
    {
        scanf("%d",&k);//这个顶点与其他k个顶点相连

        for(j=1; j<=k; j++)
        {
            scanf("%d",&temp);//temp表示与这个顶点相邻的顶点
            input[i][temp] = 1;
        }
    }
    return vertexNumber;
}

/**
   判断是不是连通图、是返回true 不是返回false
*/
bool isConnected(int input[][MAX],int vertexNumber)
{
    int i,j,count;

    for(i=1; i<=vertexNumber; i++)
    {
        tempArray[i] = 0;
    }

    //从第一个顶点开始遍历、看能不能找到所以的顶点、其实也可以从随便哪个顶点开始。
    tempArray[1] = 1;

    count = 0;
    for(i=1; i<=vertexNumber; i++)
    {
        if(1 == tempArray[i])
        {
            for(j=1; j<=vertexNumber; j++)
            {
                if(0 == tempArray[j] && 1 == input[i][j])  //表明i、j相连 并且还没有遍历j
                {
                    tempArray[j] = 1;
                    count++;
                }
            }
        }
    }

    if(vertexNumber - 1 == count)
    {
        return true;
    }
    else
    {
        return false;
    }
}


/**
   判断是不是关节点
*/

bool isArticulationPoint(int input[][MAX],int vertexNumber,int vertex)
{
    int i,j,row,col;
    row = 1;

    for(i=1; i<=vertexNumber; i++)
    {
        col = 1;
        if(i != vertex)
        {
            for(j=1; j<=vertexNumber; j++)
            {
                if(j != vertex)
                {
                    tempArray2[row][col] = input[i][j];
                    col++;
                }
            }

            row++; //注意这里,开始写在if语句后面、显然就逻辑错误了
        }
    }

    //printArray(tempArray2,vertexNumber-1);
    return isConnected(tempArray2,vertexNumber-1);//少了一个顶点
}


/*
void printArray(int array[][MAX],int n)
{
    printf("\n");
    int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            printf("%d ",array[i][j]);
        }

        printf("\n");
    }

}
*/