int Religions(int n,int m,int* record)
{
    int *ip;
    int i,iNum,iCount=0;
    ip=new int[n];
    for(i=0;i<m;i++)
    {
        iNum=(record[i*2]>record[i*2+1]?record[i*2]:record[i*2+1]);
        ip[iNum-1]=1;
    }
    for(i=0;i<n;i++)
        if(ip[i]!=1)
            iCount++;
    return iCount;
}
//与前面6楼的思路相同，省去了初始化，更快一些，但是总让我有种不安全的感觉，
//但也许只是偏见。

int Religions(int n,int m,int *record)
{
    int *a,*b;
    int i,j,k,l,t,h,sum=0;
    b=(int *)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        b[i]=0;
    }    
    for(i=0,j=1;i<m;i++)
    {
        if(b[record[i*2]-1]==0&&b[record[i*2+1]-1]==0)
        {
            b[record[i*2]-1]=b[record[i*2+1]-1]=j;
            j++;
        }else{
            if(b[record[i*2]-1]==0)
            {
                b[record[i*2]-1]=b[record[i*2+1]-1];
            }else{    
                if(b[record[i*2+1]-1]==0)  
                {
                    b[record[i*2+1]-1]=b[record[i*2]-1]; 
                }else{  
                    if(b[record[i*2]-1]>b[record[i*2+1]-1])
                    {
                        h=b[record[i*2]-1];
                        for(t=0;t<n;t++)
                        {                     
                            if(b[t]==h)
                            {                       
                                b[t]=b[record[i*2+1]-1];
                            }
                        }              
                    j--;        
                    }else{
                        if(b[record[i*2]-1]<b[record[i*2+1]-1])
                        {
                            h=b[record[i*2+1]-1];
                            for(t=0;t<n;t++)
                            {
                                if(b[t]==h)
                                {
                                    b[t]=b[record[i*2]-1];
                                }
                            }    
                        j--;
                        }
                    }
                }
            }
        }
    }                             
    for(i=0;i<n;i++)
    {
        if(b[i]==0) 
        {
            sum++;
        }
    }        
    return sum+j-1;
} 

来不及测试了，可能有些错误，只能有空再来改了
输入的数据是要按照顺序来的，就象给出的例子，如果不是顺序的话要先排下序，小弟来不及排了，有空补上。

#define N 50000  //不知道要抽多少个数据，就定义了50000
int Religions(int n,int m,int* record){
    int count = 1;
    int i;
    int flag[N];  //记录被抽到的，第一组以及和第一组都有联系的记为1，接着2。3。
    int select[N];  //记录是否被抽到
    int *head = record;;
    int *temp;
    memset(flag,0,N);
    memset(select,0,N);
         //找出被抽到的有几种宗教
    for (i=0; i<m*2; i=i+2,record++){
        if (flag[*record-1] == 0){  //还未抽到过
            flag[*record++-1] = count;
            flag[(*record)-1] = count;
            record--;
            count++;
        } else {
            temp = record+1;
            flag[*temp-1] = flag[*record-1];
        }
        select[*record-1] = 1;
        select[*(++record)-1] = 1;
    }

    count--;
         剩余的没抽到的都各自一个宗教
    for (i=0; i<n; i++,head++){
        if(select[i] == 0){
            count++;
        }
    }
    return count;
}

/***************************************************
Celeron 466MHz,160M SDR,Windows Me,VC++6.0,Release
当n=20000,m=500000时，时间4~7秒.
当n=25000,m=500000时，时间9~13秒.
****************************************************/
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

int Religions(int n,int m,int* record)
{
    int count=n;    //初始状态最多信仰数为人数n
    int i;
    //初始状态人最多的情况是每个人信仰不同,信仰分别编号
    int *team;
    team=new int[n+1];
    for(i=1;i<=n;i++)
        team[i]=i;
    //通过检查数组record[]有相同信仰的人归为一组
    for(i=0;i<m;i++)
    {
        int r1=record[2*i];
        int r2=record[2*i+1];
        //如果r1,r2两个人所在的组不同的话，两组合为一组,宗教数减一
        if(team[r1]!=team[r2])
        {
            int big,small,j;
            count--;
            if(team[r1]>team[r2])
            {
                big=team[r1];
                small=team[r2];
            }
            else
            {
                big=team[r2];
                small=team[r1];
            }
            for(j=1;j<=n;j++)
            {
                if(team[j]==big)
                    team[j]=small;
            }
        }
    }
    return count;
}
void main()
{
    //*
    int n=10;
    int m=4;
    int record[]={1,2,4,5,4,8,5,8};
    /*/
    int n=25000;
    int m=500000;
    int *record;
    record=new int[m*2];    
    srand((unsigned int)time(NULL));
    for(int i=0;i<m;i++)
    {
        record[2*i]=int(1+n*rand()/(RAND_MAX+1.0));
        record[2*i+1]=int(1+n*rand()/(RAND_MAX+1.0));
    }
    //*/
    time_t begin,tm;
    int result;
    begin=time(NULL);
    result=Religions(n,m,record);
    tm=time(NULL)-begin;
    cout<<result<<"   "<<tm<<"s"<<endl;
}

//这一题是典型的求maximum partition set

int Religions(int n,int m,int* record)
{
    int total = n;
    int *ptree = new int[n+1];
    memset(ptree, 0, (n+1) * sizeof(int));

    for (int i=0; i<m; i++)
    {
        int num1 = record[i + i];
        int num2 = record[i + i + 1];

        int head1 = num1;
        int last  = num1;
        while (ptree[head1] != 0)
        {
            int next = ptree[head1];
            ptree[last] = next;
            last  = head1;
            head1 = next;
        }
        if ((ptree[num1] != head1) && (num1 != head1))
            ptree[num1] = head1;

        int head2 = num2;
        last = num2;
        while (ptree[head2] != 0)
        {
            int next = ptree[head2];
            ptree[last] = next;
            last = head2;
            head2 = next;
        }
        if ((ptree[num2] != head2) && (num2 != head2))
            ptree[num2] = head2;

        if (head1 != head2)
        {
            total--;
            if (head1 < head2)
            {
                ptree[head2] = head1;
                ptree[num2] = head1;
            }
            else    //head1 > head2
            {
                ptree[head1] = head2;
                ptree[num1] = head2;
            }
        }
    }

    return total;
}

#include <stdio.h>
#include <memory.h>
typedef unsigned short int U16;
U16 node[50001];
int DifferRoot(U16 a,U16 b)
{
    if(a==b)
        return 0;
    U16 ra=a,rb=b;
    while(node[ra])
        ra=node[ra];
    while(node[rb])
        rb=node[rb];
    if(node[a])
        node[a]=ra;
    if(node[b])
        node[b]=rb;
    if(ra==rb)
        return 0;
    node[rb]=ra;
    return 1;
}
int Religions(int n,int m,int* record)
{
    memset(node,0,(n+1)*sizeof(U16));
    for(int i=0;i<m;++i)
    {
        if(DifferRoot((U16)(record[i*2]),(U16)(record[i*2+1])))
            n--;
    }
    return n;
}
int main(void)
{
    int record[]=
{2, 3,
4, 5,
4, 8,
5, 8}



;

    printf("%d\n",Religions(10,4,record));
    return 0;
}

[color=0000FF]int[/color] Religions([color=0000FF]int[/color] n,[color=0000FF]int[/color] m,[color=0000FF]int[/color]* record)
{
    [color=0000FF]int[/color] *g;                    [color=008000]//g对应于record,存放同位置的record中的学生的宗教分组类别[/color]
    [color=0000FF]int[/color] i,j,k;                 [color=008000]//临时数字[/color]
    [color=0000FF]int[/color] m1=0,m2=0;             [color=008000]//用于暂时存放一对学生中的宗教分组情况[/color]
    [color=0000FF]int[/color] count=1;               [color=008000]//递增产生宗教的分组号[/color]
    [color=0000FF]int[/color] result=n;              [color=008000]//返回的结果值[/color]
    
    g=([color=0000FF]int[/color]*)malloc([color=0000FF]sizeof[/color]([color=0000FF]int[/color])*m*2);

    [color=008000]//循环以成对形式处理学生情况[/color]
    [color=0000FF]for[/color](i=0;i<m;i++)
    {
        [color=0000FF]for[/color](j=0;j<2*i;j++)
         {
             [color=008000]//处理一对中的第一个，如果之前出现过该学号，设置该学号宗教分组为上次该学号宗教分组[/color]
             [color=0000FF]if[/color](*(record+2*i)==*(record+j))
             {
                 m1=*(g+j);
                 [color=0000FF]break[/color];
             }
         }

         [color=0000FF]for[/color](j=0;j<2*i;j++)
         {
             [color=008000]//处理一对中的第二个，如果之前出现过该学号，设置该学号宗教分组为上次该学号宗教分组[/color]
             [color=0000FF]if[/color](*(record+2*i+1)==*(record+j))
             {
                 m2=*(g+j);
                 [color=0000FF]break[/color];
             }
         }

         [color=008000]//如果两个学号之前都没有出现过，则重新分配给他们一个相同的宗教组别[/color]
         [color=0000FF]if[/color](m1==0&&m2==0)
         {
             
             *(g+2*i+1)=*(g+2*i)=count++;
             result--;
         }
         
         [color=008000]//如果第二个之前出现过，则设置第一个的宗教组别等于第二个，第二个等于之前[/color]
         [color=0000FF]else if[/color](m1==0&&m2!=0)
         {
             
             *(g+2*i+1)=*(g+2*i)=m2;
             m2=0;
             result--;
         }

         [color=008000]//如果第一个之前出现过，则设置第二个的宗教组别等于第一个，第一个等于之前[/color]
         [color=0000FF]else if[/color](m1!=0&&m2==0)
         {
             
             *(g+2*i+1)=*(g+2*i)=m1;
             m1=0;
             result--;
         }

         [color=008000]//如果都在之前出现过[/color]
         [color=0000FF]else[/color] 
         {
             *(g+2*i+1)=*(g+2*i)=m1;
             [color=008000]//如果以前出现的组别不同，则将第二个学生的原所有组成员换成第一个学生的组成员[/color]
             [color=0000FF]if[/color](m1!=m2)
             {
                [color=0000FF]for[/color](k=0;k<2*m;k++)
                {
                  [color=0000FF]if[/color](*(g+k)==m2)
                  {
                  *(g+k)=m1;
                  }
                }
                 result--;
             }
             m1=m2=0;
        }
             
    }
   
    free(g);
    [color=0000FF]return[/color] result;
}

/* 用邻接表表示法的图来实现 */
#include <assert.h>
#include <stdio.h>

#define MAXVEX        50001

typedef int    VexType;

typedef struct EdgeNode
{    
    int            endvex;        /* 相邻顶点字段 */
    struct        EdgeNode    *nextedge;    /* 链字段 */
}EdgeNode, *PEdgeNode;        /* 边表 */

typedef struct
{    
    VexType     vertex;        /* 顶点信息 */
    PEdgeNode     edgelist;    /* 边表头指针 */
}VexNode;        /* 顶点表 */

typedef struct
{    
    VexNode     vexs[MAXVEX];    /* 顶点表 */
    int         vexNum;        /* 图的顶点个数 */
    int            edgeNum;
}Graph;

/* 创建图 */
void CreateGraph(Graph *g, int n, int m, int *record) 
{
    int            i, j, k;
    EdgeNode    *p;

    g->vexNum  = n;
    g->edgeNum = m;

    // 加入所有顶点
    for(i=0; i<g->vexNum; i++)
    {
        g->vexs[i].vertex   = i+1;
        g->vexs[i].edgelist = NULL;
    }

    /* 构造所有的边 */
    for(k=0; k<g->edgeNum; k++)
    {    
        p = new EdgeNode;
        assert(p);    
        i = record[2*k] - 1;
        j = record[2*k+1]-1;
        // 加入<i, j>
        p->endvex = j;
        if(g->vexs[i].edgelist == NULL)
        {    
            g->vexs[i].edgelist = p;
            p->nextedge = NULL;
        }
        else
        {
            p->nextedge = g->vexs[i].edgelist->nextedge;
            g->vexs[i].edgelist->nextedge = p;
        }
        // 加入<j, i>
        p = new EdgeNode;
        assert(p);    
        p->endvex = i;
        if(g->vexs[j].edgelist == NULL)
        {    
            g->vexs[j].edgelist = p;
            p->nextedge = NULL;
        }
        else
        {
            p->nextedge = g->vexs[j].edgelist->nextedge;
            g->vexs[j].edgelist->nextedge = p;
        }

    }
}    


/* 从vi出发进行深度优先搜索，图采用邻接表表示法 */
void dFSInList(Graph * pGraph, bool visited[], int i)
{
    PEdgeNode     p;

    visited[i] = true;
    p = pGraph->vexs[i].edgelist; /* 取边表中的第一个边结点 */
    while(p != NULL)
    {
        /* 该顶点的相邻顶点未被访问 */
        if(visited[p->endvex] == false) 
            /* 继续进行深度优先搜索 */
            dFSInList(pGraph, visited, p->endvex);     
        p=p->nextedge; /* 取边表中的下一个边结点 */
    }
}  

/* 深度优先搜索 */
int traverDFS(Graph* pGraph)
{
    int        i;
    bool    visited[MAXVEX];
    int        count = 0;

    for(i=0;i<pGraph->vexNum;i++)    /* 初始化数组visited */
        visited[i]=false;

    for(i=0; i<pGraph->vexNum; i++)
    {
        if(visited[i] == false)
        {
            ++count;
            dFSInList(pGraph, visited, i);
        }
    }

    return count;
}

/* 销毁图 */
void DestroyGraph(Graph *g)
{
    EdgeNode    *p, *temp;

    for(int i=0; i<g->vexNum; ++i)
    {
        p = g->vexs[i].edgelist;
        while(p != NULL)
        {
            temp = p->nextedge;
            delete p;
            p = temp;
        }
    }
}


int Religions(int n, int m, int* record)
{
    Graph        g;

    CreateGraph(&g, n, m, record);
    int        count = traverDFS(&g);

    DestroyGraph(&g);
    return count;
}

/*//第一题：*/
int Religions(int n,int m,int* record)    /*//本函数没有边界检查，调用是要注意！！*/
{
    int student[50001]={0};          /*//student[i]表示第i个学生是否在record中，0表示不在，1表示在,student[0]为record中宗教的最大可能值*/
    int  sum=0;        /*//sum为所有学生的宗教数的最大可能值*/
    int i=0;

    for ( i=0;i<m;i++)        //算法：若i组学生在record中，且未被登记，则登记（student[0]加1），并置标志，循环结束后student[0]即为record中的学生的最大可能宗教数*/

    {
        if(!((student[record[2*i]] || student[record[2*i+1]])))    /*//若record中第i对学生宗教没有登记，则登记*/
            ++student[0];
        
        student[record[2*i]] = student[record[2*i+1]] = 1;        /*//更改标志*/
    }

    for (i=1;i<50001;++i)            /*n减去数组record后50000项，即为不在record中的学生数*/
        n -= student[i];

    sum = n + student[0];            /* sum完全可以省略，为方便起见（看起来舒服，谁会喜欢 return n + student[0]？？？），就不省了*/

                                    /* 不在record中的学生可能一人个宗教，宗教数最大为 n + stufent[0]*/

    return sum;
}

呵呵，典型的连通性问题：我是采用的路径压缩的加权快速并集法。
/* 环境：vc6.0＋xp */
int Religions(int n,int m,int *record)
{
    int i,j,k=0;
    int *id,*sz;//id里保存指向节点的索引，
                //sz里保存每个节点所连接的节点数。
    //为id，sz分配内存
    id=(int *)calloc(n+1,sizeof(int));
    if(id==NULL)
    {
        printf("id:Out of space!\n");
        exit(1);
    }
    sz=(int *)calloc(n+1,sizeof(int));
    if(sz==NULL)
    {
        printf("sz:Out of space!\n");
        exit(1);
    }
    //数组初始化。    
    for(i=1;i<=n;i++)
    {
        id[i]=i;
        sz[i]=1;
    }    
    while(k<m)
    {
        for(i=record[2*k];i!=id[i];i=id[i])
            id[i]=id[id[i]];  //指向根节点
        for(j=record[2*k+1];j!=id[j];j=id[j])
            id[j]=id[id[j]];
        k++;
        if(i==j)
            continue;
        if(sz[i]<sz[j])  //使节点指向节点数较多的根节点
        {
            id[i]=j;sz[j]+=sz[i];
        }
        else
        {
            id[j]=i;sz[i]+=sz[j];
        }
        
    }
    for(i=1;i<=n;i++)
        if(sz[i]>1)
            n-=(sz[i]-1);
    free(id);free(sz);
    return n;
}