這道題是用并查集來解例获。并查集可以高效的查找某個元素是否屬于一個集合。
敲代碼過程中一次遇到了如下問題：

new 的使用問題

想開辟一塊放100個整形變量的空間范抓，我這樣寫的：

 int *father = new  int(100);

給這個int數(shù)組賦值的時候一直報錯冯丙，覺得自己一定是開辟空間的時候搞錯了。
果然咖熟，new A（100）的寫法是說，把變量的值初始化成100柳畔。
想要開辟100個A類型的變量空間馍管，應(yīng)該這么寫：

int *father=new int[100];

按照《挑戰(zhàn)程序設(shè)計競賽》思路寫出的代碼超時

我在看這邊書的時候就一直有一個疑問，作者是不是由于原先寫慣了C語言薪韩，C++里面的cin和cout用著不順手确沸，所以還特別費事兒的加上#include<cstdio>的頭文件，并且輸入輸出用printf和scanf躬存。
今天我按照這本書的思路寫了1182這一題张惹，發(fā)現(xiàn)一直超時，把cin改成scanf就AC了岭洲，百度了一下發(fā)現(xiàn)很多文章討論它倆性能的差異宛逗。得出的結(jié)論是，程序設(shè)計題盡量用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;
}