食物链POJ1182总结

这道题是用并查集来解。并查集可以高效的查找某个元素是否属于一个集合。
敲代码过程中一次遇到了如下问题：

new 的使用问题

想开辟一块放100个整形变量的空间，我这样写的：

 int *father = new  int(100);

给这个int数组赋值的时候一直报错，觉得自己一定是开辟空间的时候搞错了。
果然，new A（100）的写法是说，把变量的值初始化成100。
想要开辟100个A类型的变量空间，应该这么写：

int *father=new int[100];

按照《挑战程序设计竞赛》思路写出的代码超时

我在看这边书的时候就一直有一个疑问，作者是不是由于原先写惯了C语言，C++里面的cin和cout用着不顺手，所以还特别费事儿的加上#include<cstdio>的头文件，并且输入输出用printf和scanf。
今天我按照这本书的思路写了1182这一题，发现一直超时，把cin改成scanf就AC了，百度了一下发现很多文章讨论它俩性能的差异。得出的结论是，程序设计题尽量用scanf而不是cin。

源代码

#include <iostream>
#include <cstdio>
using namespace std;

class union_find
{
private:
        int* father;
        int* height;
        int n;
public:
    union_find(int n)
    {

        this->n = n;

        father = new int[n];

        height = new int[n];
        for(int i=0;i<n;i++)
        {

            father[i]=i;
            height[i]=0;
        }

    }
    ~union_find()
    {
        delete []father;
        delete []height;
    }
    int _find(int x)
    {
        if(x>=n)
        {

            return 0;
        }
        if(father[x]==x)
        {
            return x;
        }
        else
        {
            return father[x]=(_find(father[x]));
        }
    }
    void unite(int x,int y)
    {
        if(x>=n||y>=n)
        {

            return;
        }
        x = _find(x);
        y = _find(y);
        if(height[x]<height[y])
        {
            father[x]=y;
        }
        else
        {
            father[y]=x;
            if(height[x]==height[y])
            {
                height[x]++;
            }
        }
    }

    bool same(int x,int y)
    {
        return _find(x) == _find(y);
    }

};



int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
   // cin>>n>>k;


    union_find f(n*3);

    int ans=0;

    for(int i=0;i<k;i++)
    {
        int t,x,y;
        //cin>>t>>x>>y;
        scanf("%d%d%d",&t,&x,&y);

        x = x-1;
        y = y-1;

        if(x<0||x>=n||y<0||y>=n)
        {

            ans++;
            continue;
        }
        if(t==1)
        {
            if(f.same(x,y+n)||f.same(x,y+2*n))
            {

                ans++;
                continue;
            }
            else
            {
                f.unite(x,y);
                f.unite(x+n,y+n);
                f.unite(x+2*n,y+2*n);
            }
        }
        else
        {
            if(f.same(x,y)||f.same(y,x+n))
            {
                ans++;
                continue;
            }
            else
            {
                f.unite(x,y+n);
                f.unite(x+n,y+2*n);
                f.unite(x+2*n,y);
            }
        }
    }
    cout<<ans<<endl;
    return ans;
}