Interesting Computer Game

题意：
有n轮游戏，每轮你可以从二个数中选择其中一个数，求你选择数的种类最多为多少？

思路：
先离散化数据，然后我们将每一轮游戏当成一条边，如果成环了，则该环所以端点都能选择，且与环连通的点也能全部选择，你画个图就很容易理解了，由环往外扩散。如果连通块无环，则有一个端点无法选择。所以我们用并查集来处理数据，有环则给该连通块做个标记。

代码：

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int inf=1000000007;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

struct w
{
    int x, y;
} w[100005];

int ma[200005], ran[200005], shu[200005], ans, pre[200005], fu[200005];

map<int,int> mp;

bool cmp(struct w a,struct w b)
{
    return a.y<b.y;
}

void inti(int k)
{
    for(int i=1;i<=k;i++)
    {
        pre[i]=i;
        ran[i]=0;
    }
}

int find(int x)
{
    if(pre[x]==x)
    {
        return  x;
    }
    return pre[x]=find(pre[x]);
}

int unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        fu[y]=fu[y]|fu[x];
        fu[x]=fu[x]|fu[y];
        if(ran[y]>ran[x])
        {
            pre[x]=y;
        }
        else
        {
            if(ran[x]==ran[y])
            {
                ran[x]++;
            }
            pre[y]=x;
        }
    }
}

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

int main()
{
    int t;
    t=read();
    for(int o=1; o<=t; o++)
    {
        int n, ji=0;
        n=read();
        memset(fu,0,sizeof(fu));
         memset(ma,0,sizeof(ma));
        ans=0;
        for(int i=0; i<n; i++)
        {
            w[i].x=read();
            w[i].y=read();
            shu[ji++]=w[i].x;
            shu[ji++]=w[i].y;
        }
        sort(shu,shu+ji);
        int k=1;
        for(int i=0; i<ji-1; i++)
        {
            if(shu[i]!=shu[i+1])
            {
                k++;
                mp[shu[i]]=k-1;
            }
        }
        mp[shu[ji-1]]=k;
        k++;
        inti(k);
        for(int i=0; i<n; i++)
        {
            w[i].x=mp[w[i].x];
            w[i].y=mp[w[i].y];
            if(same(w[i].x,w[i].y))
            {
                fu[find(w[i].x)]=1;
            }
            else
            {
                unite(w[i].x,w[i].y);
            }
        }
        for(int i=1; i<k; i++)
        {
            ma[find(i)]++;
        }
        for(int i=1; i<k; i++)
        {
            if(ma[i]>0)
            ans=ans+ma[i]+fu[i]-1;
        }
        mp.clear();
        printf("Case #%d: %d\n",o,ans);
    }
    return 0;
}