国际大学生程序设计竞赛例题_5.8 基本的图问题

1,题意:
给定一个整数序列1到n.
给m个连边的命令(s,e):表示:第s个到第e个之间的最大和最小数连起来.
k个询问:(x,y)点x和y是否连通.

2,解题思路:
(1)RMQ问题,求出s和e
(2)并查集:Union(s,e)
(3)结果:Find_Set(x)==Find_Set(y)?

3,严重超时??????

#include <iostream>
#include <cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

#define VMAX 101100 //节点个数
int father[VMAX]; //father[x]:元素x的父节点
int rank[VMAX]; //rank[x]:x元素的秩
int input[VMAX]; //输入的序列

//并查集的相关操作
//初始化操作
void Make_Set(int x)
{
    father[x]=x;
    rank[x]=0;
}
//递归实现
int Find_Set_R(int x)
{
    if(x!=father[x])
        //通过回溯,完成路径压缩
        father[x]=Find_Set_R(father[x]);
    return father[x];
}
//非递归实现
int Find_Set(int x)
{
    int r=x;
    while(r!=father[r])
        r=father[r];

    //路径压缩:把x上面的所有节点的父节点都指向祖先节点
    int temp;
    while(x!=r)
    {
        temp=father[x];
        father[temp]=r;
        x=temp;
    }
    return r;
}
void Union(int x,int y)
{
    x=Find_Set(x);
    y=Find_Set(y);
    if( rank[x]>rank[y]) //通常将元素少的集合合并到元素多的集合
        father[y]=x;
    else
        father[x]=y;
    if( rank[x]==rank[y] )
        rank[y]++;
}

//RMQ的相关操作
int dpmax[VMAX][20];
int getmax(int a,int b)
{
    return a>b? a:b;
}
void make_max_rmq(int n,int b[])
{
    memset(dpmax, 0, sizeof(dpmax));
    int i,j;
    for(i=0;i<n;i++)
        dpmax[i][0]=b[i];
    for(j=1;(1<<j)<=n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            dpmax[i][j]=getmax(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
}
int get_max_rmq(int s,int v)
{
    int k=(int)(log((v-s+1)*1.0)/log(2.0));
    return getmax(dpmax[s][k],dpmax[v-(1<<k)+1][k]);
}

int dpmin[VMAX][20];
int getmin(int a,int b)
{
    return a<b? a:b;
}
void make_min_rmq(int n,int b[])
{
    memset(dpmin, 0, sizeof(dpmin));
    int i,j;
    for(i=0;i<n;i++)
        dpmin[i][0]=b[i];
    for(j=1;(1<<j)<=n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            dpmin[i][j]=getmin(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
}
int get_min_rmq(int s,int v)
{
    int k=(int)(log((v-s+1)*1.0)/log(2.0));
    return getmin(dpmin[s][k],dpmin[v-(1<<k)+1][k]);
}

int main()
{
    int n; //顶点个数
    int c=0; //测试次数
    int m;//边数
    int u,v;//边的两个端点
    int k; //询问次数
    freopen("5.8.in","r",stdin);
    while (cin>>n)
    {
        if (c != 0)
            cout<<endl;
        c++;
        cout << "CASE " << c << endl;
        for(int i = 0; i < n; i++)
        {
            cin >> input[i];//输入序列
            input[i]--; //换成0到n-1;
            Make_Set(input[i]); //并查集初始化
        }
        cin >> m;
        make_min_rmq(n,input);
        make_max_rmq(n,input);
        for(int i = 0; i < m; i++)
        {
            cin >> u >> v;
            u--,v--;
            u = get_min_rmq(u, v);
            v = get_max_rmq(u, v);
            Union(u,v);
        }
        cin >> k;
        for (int i = 0; i < k; i++)
        {
            cin >> u >> v;
            u--,v--;
            //if(Find_Set(u)==Find_Set(v))
            if (Find_Set_R(u) == Find_Set_R(v))
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
}