HDU 1272 小希的迷宫（水题）

题意：

　　其实就是让你判断一个图是否为树，要求不能有孤立的点（没有这中情况），且只能有1个连通图，且边数+1=点数，且每个点都有边（不可能只有1个点出现）。

思路：

　　有可能出现连续的4个0，也就是有测试例子是完全没有点的，也没有边，要打印Yes！记录下所有点（去重），记录下每个点的度数，如果有n个点，n-1条边，且每点都是有边连着的，再判断其只有一个连通图就行了。因为只有n-1条边，所以当只有一个连通图时，必不会有环的产生。

判断是否只有一个连通图的方法：

（1）BFS（可用）

（2）DFS(有10万点，可能爆栈)

（3）并查集（可用）

（4）prim、kruscal生成一个树，所有点和所有边都要用上。

（5）Dijkstra、Bellman-Ford 求单点到其他点的路径长，如果有两点的路径为无穷则证明有点不可达。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=100005;
 4 const int mod=0x7f7f7f7f;
 5 int num[N];
 6 /*
 7 仅仅靠边数+点数来断定是否为树，应该是错的。测试数据：
 8     1 2 3 4
 9     3 5 4 5
10     0 0
11 */
12 int main()
13 {
14     freopen("e://input.txt", "r", stdin);
15     int n, a, b;
16     while(1)
17     {
18         memset(num,0,sizeof(num));
19         int cnt=0, siz=0;
20         while(scanf("%d%d",&a,&b),a+b>0)
21         {
22             if(!num[a])
23             {
24                 siz++;    //点数
25                 num[a]++;
26             }
27             if(!num[b])
28             {
29                 siz++;
30                 num[b]++;
31             }
32             cnt++;  //边数
33         }
34         if(a==-1 && b==-1)    break;
35         if(!cnt||cnt+1==siz)    printf("Yes
");
36         else            printf("No
");
37 
38     }
39     return 0;
40 }

AC的错误代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=100005, mod=0x7f7f7f7f;
 4 unordered_map<int,int> mapp;//将点编号映射到从1开始的连续的编号
 5 int pre[N];
 6 int find(int a) //查
 7 {
 8     int tmp=a;
 9     while(pre[tmp]!=tmp)    tmp=pre[tmp]; //找到a的祖先
10     pre[a]=tmp; //改其祖先
11     int p;
12     while(a!=tmp)   //从a到tmp所经过的点，改其全部祖先
13     {
14         p=pre[a];
15         pre[a]=tmp;
16         a=p;
17     }
18     return tmp;
19 }
20 
21 void joint(int a,int b) //并
22 {
23     a=find(a);
24     b=find(b);
25     if(a!=b)    pre[a]=b;
26 }
27 
28 void init() //初始化pre，不知道点个数，所以只能这样了
29 {
30     for(int i=1; i<=N; i++)    pre[i]=i;
31 }
32 
33 int istree(int n)    //每个房间都是连着的
34 {
35     for(int i=1; i<=n; i++)    find(i); //防止漏网之鱼
36     for(int i=1; i<n; i++)     if(pre[i]!=pre[i+1]) return 0;   //不是同个领导的
37     return 1;
38 }
39 
40 int main()
41 {
42     freopen("e://input.txt", "r", stdin);
43     int n, a, b;
44     while(1)
45     {
46         memset(pre,0,sizeof(pre));
47         mapp.clear();
48         init();         //初始化pre[]祖先列表
49         int cnt=0, j=0;
50 
51         while(scanf("%d%d",&a,&b),a>0&&b>0)
52         {
53                     //cout<<"123"<<endl;
54             if(!mapp[a])    mapp[a]=++j;    //重新编号
55             if(!mapp[b])    mapp[b]=++j;
56 
57             joint(mapp[a], mapp[b]);
58             cnt++;         //边数
59         }
60         if(a==-1 || b==-1)    break;
61 
62         if(!cnt)    printf("Yes
");    //坑
63         else if(cnt+1!=j)    printf("No
");//边多了肯定不行
64         else
65         {
66             if(istree(j))    printf("Yes
");
67             else    printf("No
");
68         }
69     }
70     return 0;
71 }

AC代码（并查集实现）

HDU 1272 小希的迷宫 （水题）

HDU 1272 小希的迷宫（水题）