HDU5631 Rikka with Graph

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:  Yuta has a non-direct graph with n vertices and n+1 edges. Rikka can choose some of the edges (at least one) and delete them from the graph.  Yuta wants to know the number of the ways to choose the edges in order to make the remaining graph connected.  It is too difficult for Rikka. Can you help her? Input The first line contains a number  T(T≤30) T(T≤30)——The number of the testcases.  For each testcase, the first line contains a number  n(n≤100) n(n≤100).  Then n+1 lines follow. Each line contains two numbers  u,v u,v , which means there is an edge between u and v. Output For each testcase, print a single number. Sample Input 1 3 1 2 2 3 3 1 1 3 Sample Output 9

Status Accepted Time 499ms Memory 1608kB Length 1574 Lang G++ Submitted 2017-04-19 12:43:22 题目大意：

具有n个顶点和n+1个边的非连通图形。可以选择一些边（至少一个），并从图中删除它们。想得出选择边缘的方法的数量，以使剩余的图形连通。

输入：

line 1：T个样例

line 2：N个顶点

line 3：N+1行边

输出：

选择删除边数的方法数量。

解题思路：

1.建立一个结构体来存储这N个顶点

struct number{     int x,y;     int flag; }a[107];

int s[107]; //来存储父节点

int num[107];     ///来存储秩

2.因为N个顶点的话，最少必须有N-1条边进行连通。所以两个循环来进行选择删除边数。

for(i=0;i<=n;i++)         {             a[i].flag=0;             //printf("删除第%d条边!\n",i+1);              judge();             for(j=i+1;j<=n;j++)             {                 a[j].flag=0;                 //printf("删除第%d条边!\n",j+1);                  judge();                 //printf("恢复第%d条边!\n",j+1);                 a[j].flag=1;             }             a[i].flag=1;             //printf("恢复第%d条边!\n",i+1);         }

3.判断删除两条边数后，是否是一个连通的图形。

num=0;         for(j=1;j<=n;j++)         {             if(s[j]==j)                 num+=1;         }         if(num==1)         {             //printf("找到一种方案!\n");              number+=1;             }

也就是说，在父节点数组中，只有一个节点的父节点是它本身时，其余节点都是该节点的子节点，该方案就满足条件。

坑点总结：

1.只要头脑清醒，该题不是问题。

程序代码：

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; struct number{ int x,y; int flag; }a[107]; int s[107]; int num[107]; int n,x,x1; int number; int find(int i) { while(i!=s[i]) i=s[i]; return i; } void judge() { int i,j,p,q; int count; for(i=1;i<=n;i++) s[i]=i; for(i=0;i<=n;i++) { if(a[i].flag==1) { p=find(a[i].x); q=find(a[i].y); if(q!=p) s[p]=q; //printf("%d的父节点是%d\n",p,q); } } count=0; for(j=1;j<=n;j++) { if(s[j]==j) count+=1; if(count>1) break; } if(count==1) //printf("找到一种方案!\n"); number++; } int main() { int t,i,j; scanf("%d",&t); while(t--) { number=0; scanf("%d",&n); for(i=0;i<=n;i++) { scanf("%d%d",&x,&x1); a[i].x=x; a[i].y=x1; a[i].flag=1; } for(i=0;i<=n;i++) { a[i].flag=0; //printf("删除第%d条边!\n",i+1); judge(); for(j=i+1;j<=n;j++) { a[j].flag=0; //printf("删除第%d条边!\n",j+1); judge(); //printf("恢复第%d条边!\n",j+1); a[j].flag=1; } a[i].flag=1; //printf("恢复第%d条边!\n",i+1); } printf("%d\n",number); } return 0; }