Chinaunix首页 | 论坛 | 博客
  • 博客访问: 506067
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-09-20 18:47:40

/**
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
*/


点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #define MAX 100

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

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

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

  16.     scanf("%d",&cases);

  17.     while(cases--)
  18.     {
  19.         flag = false;
  20.         vertexNumber = init(input);
  21.         if(isConnected(input,vertexNumber))
  22.         {
  23.             for(i=1; i<=vertexNumber; i++)
  24.             {
  25.                 if(!isArticulationPoint(input,vertexNumber,i))
  26.                 {
  27.                     if(!flag)
  28.                     {
  29.                         printf("%d",i);
  30.                         flag = true;
  31.                     }
  32.                     else
  33.                     {
  34.                         printf(" %d",i); //以后的输出多一个空格
  35.                     }
  36.                 }
  37.             }
  38.         }

  39.         if(!flag)
  40.         {
  41.             printf("None");
  42.         }

  43.         printf("\n");
  44.     }
  45.     return 0;
  46. }

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

  51.     for(i=1; i<=vertexNumber; i++)
  52.     {
  53.         for(j=1; j<=vertexNumber; j++)
  54.         {
  55.             input[i][j] = 0;
  56.         }
  57.     }

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

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

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

  75.     for(i=1; i<=vertexNumber; i++)
  76.     {
  77.         tempArray[i] = 0;
  78.     }

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

  81.     count = 0;
  82.     for(i=1; i<=vertexNumber; i++)
  83.     {
  84.         if(1 == tempArray[i])
  85.         {
  86.             for(j=1; j<=vertexNumber; j++)
  87.             {
  88.                 if(0 == tempArray[j] && 1 == input[i][j]) //表明i、j相连 并且还没有遍历j
  89.                 {
  90.                     tempArray[j] = 1;
  91.                     count++;
  92.                 }
  93.             }
  94.         }
  95.     }

  96.     if(vertexNumber - 1 == count)
  97.     {
  98.         return true;
  99.     }
  100.     else
  101.     {
  102.         return false;
  103.     }
  104. }


  105. /**
  106.    判断是不是关节点
  107. */

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

  112.     for(i=1; i<=vertexNumber; i++)
  113.     {
  114.         col = 1;
  115.         if(i != vertex)
  116.         {
  117.             for(j=1; j<=vertexNumber; j++)
  118.             {
  119.                 if(j != vertex)
  120.                 {
  121.                     tempArray2[row][col] = input[i][j];
  122.                     col++;
  123.                 }
  124.             }

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

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


  131. /*
  132. void printArray(int array[][MAX],int n)
  133. {
  134.     printf("\n");
  135.     int i,j;
  136.     for(i=1; i<=n; i++)
  137.     {
  138.         for(j=1; j<=n; j++)
  139.         {
  140.             printf("%d ",array[i][j]);
  141.         }

  142.         printf("\n");
  143.     }

  144. }
  145. */

阅读(664) | 评论(0) | 转发(0) |
0

上一篇:背包问题

下一篇:素数个数

给主人留下些什么吧!~~