首页 > ACM题库 > HDU-杭电 > HDU 1273 漫步森林-并查集-[解题报告] C++
2013
12-04

HDU 1273 漫步森林-并查集-[解题报告] C++

漫步森林

问题描述 :

Gardon和小希每天晚上都喜欢到屋外的森林里散步,设森林里有N块空地,任意两块空地之间都有一条小径相通。他们每次从任意一块空地出发,经过所有的空地后回到原来的空地。
由于他们都喜欢新鲜的旅行,所以他们不希望对任何一条小径经过两次。那么请问,他们最多能保证多少次这种新鲜的旅行呢?
例如(图),当N=5时,他们只能保持两次这样新鲜的旅行。

输入:

输入包含多组数据,每组数据占一行,是一个数字 N。(0<N<=1000000000)
文件以一个0结束。

输出:

对于每个输入的N,输出最多能保证新鲜旅行的次数。

样例输入:

5
0

样例输出:

2

刚开始我天真的以为是用图论做的,最后一直MLE我就很蛋疼,我说用MAP和string 映射怎么他妈就要错呢。。。真的倒塌,自己还是菜菜呀,认真学习中。。。

// by ashione 用<set>一直TLE 可能STL速度很慢吧,换成flag标记就好了。
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
#define M 100001
int root[M+1];
bool mark,flag[M+1];
void init(int n){
        for(int i=0;i<=n;i++) root[i]=i,flag[i]=false;
}       
int Find(int y){
        while(root[y]!=y)
                y=root[y];
        return y;
}
void Merge(int x,int y){
        int a=Find(x),b=Find(y);
        if(a!=b) root[a]=b;//找集合最上父节点,
        else mark=true;//是同一个,则已经形成回路
}
int main(){
        int n,i=0,a,b,max;
        init(M);
        while( scanf("%d %d",&a,&b) && a+b >=0){
                if(a+b==0){//警惕0 0 陷阱
                 cout<<"Yes"<<endl;
                 continue;
                }
                max=0;//Max无非就是为了减少下次初始化的时间和空间
                mark=false;
                while((a+b)){
                        flag[a]=flag[b]=true;
                        max=max>a?max:a;
                        max=max>b?max:b;
                        if(!mark)   // 当mark=true就证明其存在回路,就是两个集合有交点
                        Merge(a,b);
                        scanf("%d %d",&a,&b);                   
                }
                if(mark){
                 cout<<"No"<<endl;
                continue;
                }
                int cnt=0;
                for(i=1;i<=max;i++)
                        if(flag[i] && root[i]==i) cnt++;
                puts(cnt==1?"Yes":"No");
                init(max);
        }       
        return 0;

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3