Input
多组数据，每组第一行两个正整数n,m，表示有1~n这n个编号，m个关系。
接下来m行，每行两个数i, j， 1 <= i, j <= n，表示i和j是一组的。
每个编号自己和自己是一组的。
1 < n < 1000000 ，1 < m < 100000 。
Output
每组数据输出一行，一个数，表示组员最多的组的组员个数。
Sample Input
10 5
1 2
3 5
2 6
4 7
9 6
Sample Output
4
有大佬能用c语言写出来吗？？
随便将一下思路，
本人编程初学者

#include <stdio.h>

/*
数组元素
大于0 表示这个集合有多少个元素
小于0 表示这个元素属于哪个集合 
*/

int arr[1000000];

//查找元素n的根节点 
int find(int n)
{
    //如果这个元素小于0 就查找这个元素的根节点
    //如果这个元素大于0 这个元素就是要查找的元素的根节点 
    while(arr[n] < 0)
        n = -arr[n];
    return n;    
}

int main(int argc, char *argv[])
{
    int n, m;
    while(scanf("%d%d", &n, &m) == 2)
    {
        //一开始全部初始化为1 表示 每一个集合都只有1个元素 就是这个元素本身 
        for(int i=0; i<n; ++i)
            arr[i] = 1;
            
        while(m--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            int rootx = find(x);
            int rooty = find(y);
            //如果元素x 和 元素y 的根节点不一样 就合并 
            if(rootx != rooty)
            {
                //两个节点的元素个数加起来 
                arr[rootx] += arr[rooty];
                //rootx作为rooty的根节点 
                arr[rooty] = -rootx;
            }
        }
         
        int max = 0;
        for(int i=0; i<n; ++i)
        {
            if(max < arr[i])
                max = arr[i];
        }
        printf("\n%d\n", max);
    }
    return 0;
}

偷懒版的并查集
正常做法是用二叉查找树存储集合元素
显然用二叉树会写很多行代码
这题目数据规模看起来也不是特别丧心病狂
似乎大概可能也许应该或然就过了呢
做题要有梦想

这个代码简单可以,容易看懂,但时间复杂度是o(n^2),可能会超时~
有一个小小的改进方案,就是用把结点数小的加进结点大的,这样归并算法复杂度从o(n^2)降为o(n*log(n)),那正常来说可以过~

补充一下:其实有种复杂点的写法可以在o(n)的时间复杂度内实现,就是用回溯,把沿路的结点先储存下来,然后找到根结点后再把这些沿路结点标记为根结点这样写可以减少查找树的长度了,当然这样写也会相对来说复杂一点(当时向老师提这个建议被老师说这样复杂了)
~

[此贴子已经被作者于2018-5-16 22:05编辑过]

收到的鲜花

• lin5161678 于 2018-05-17 00:26 送鲜花  3朵   附言：多谢指点

似乎大概可能也许应该或然就过了呢
要有梦想啊

哈哈 嗯 你的建议看懂了
小存大 大存小都行
就是统一一个方向 查找操作会顺一个方向撸
不会像现在这样坂本横跳

这样会不会好一点~

#include <stdio.h>

/*
数组元素
大于0 表示这个集合有多少个元素
小于0 表示这个元素属于哪个集合 
*/

int arr[1000000];

//查找元素n的根节点 
int find(int n)
{
    //如果这个元素小于0 就查找这个元素的根节点
    //如果这个元素大于0 这个元素就是要查找的元素的根节点 
    while(arr[n] < 0)
        n = -arr[n];
    return n;    
}

int main(int argc, char *argv[])
{
    int n, m;
    while(scanf("%d%d", &n, &m) == 2)
    {
        //一开始全部初始化为1 表示 每一个集合都只有1个元素 就是这个元素本身 
        for(int i=0; i<n; ++i)
            arr[i] = 1;
            
        while(m--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            int rootx = find(x);
            int rooty = find(y);
            //如果元素x 和 元素y 的根节点不一样 就合并 
            if (rootx > rooty)
            {
                //两个节点的元素个数加起来 
                arr[rootx] += arr[rooty];
                //rooty作为rootx的根节点 
                arr[rooty] = -rootx;
            }
            else if (rootx < rooty)
            {
                arr[rooty] += arr[rootx];
                arr[rootx] = -rooty;
            }
        }
         
        int max = 0;
        for(int i=0; i<n; ++i)
        {
            if(max < arr[i])
                max = arr[i];
        }
        printf("\n%d\n", max);
    }
    return 0;
}

[此贴子已经被作者于2018-5-16 22:20编辑过]

看不懂你这个减少查找树长度的方案
沿路的节点存起来
然后把每一个节点的父节点都直接改成根节点?
查找树木保持在2层
是这个意思?
这个没到O(n)
查找是快了 合并操作慢了
每次合并操作要把大部分节点都遍历一遍
ps 合并操作不是比我现在的做法慢 是比原版并查集慢 并且没O(n)


-------------------------------------------

想错了
查找树2层 每次修改节点是不会超过3个 还是2个
的确是很优秀 我写写看

[此贴子已经被作者于2018-5-16 22:38编辑过]

不知道有没有bug,大概就是这样子~

PS:改了一点,大概就是这样子了~

#include <stdio.h>

/*
数组元素
大于0 表示这个集合有多少个元素
小于0 表示这个元素属于哪个集合 
*/

int arr[1000000];

//查找元素n的根节点 
int find(int n)
{
    while(arr[n] < 0)
        n = -arr[n];

    return n;    
}

void merge( int n,int m )
{    
    while(arr[n] < 0)
    {
        int t=n;
        n=-arr[n];
        arr[t]=m;
    }

}

int main(int argc, char *argv[])
{
    int n, m;
    while(scanf("%d%d", &n, &m) == 2)
    {
        //一开始全部初始化为1 表示 每一个集合都只有1个元素 就是这个元素本身 
        for(int i=1; i<n+1; ++i)
            arr[i] = 1;
            
        while(m--)
        {
            int x,y;
            scanf("%d%d", &x, &y);
            int rootx = find(x);
            int rooty = find(y);
            //如果元素x 和 元素y 的根节点不一样 就合并 
            if (rootx!=rooty)
            {
                //两个节点的元素个数加起来 
                arr[rootx] += arr[rooty];
                //rooty作为rootx的根节点 
                arr[rooty] = -rootx;
            }     
         
           merge(x,-rootx);
           merge(y,-rootx);
        }
         
         
        int max = 0;
        for(int i=0; i<n; ++i)
        {
            if(max < arr[i])
                max = arr[i];
        }
        printf("\n%d\n", max);
    }
    return 0;
}

不一定是两层,总之这个可以看出是o(n),因为重复遍历一遍的结点都会变成根结点~

[此贴子已经被作者于2018-5-18 05:42编辑过]

#include <stdio.h>

int arr[1000010];
int index;
int mask[10];

int find(int n)
{
    while(arr[n] < 0)
    {
        mask[index++] = n;
        n = -arr[n];
    }
    return n;    
}

int main(int argc, char *argv[])
{
    int n, m;
    while(scanf("%d%d", &n, &m) == 2)
    {
        //发现一个bug 编号1~n 所以下标要1~n
        //for(int i=0; i<n; ++i)
        for(int i=0; i<n+1; ++i)
            arr[i] = 1;
            
        while(m--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            index = 0;
            int rootx = find(x);
            int rooty = find(y);
            if(rootx != rooty)
            {
                arr[rootx] += arr[rooty];
                arr[rooty] = -rootx;
                for(int i=0; i<index; ++i)
                    arr[mask[i]] = -rootx;
            }
            //我发现 只有2层 我不需要顾及方向了 随便横跳 坂本横跳
        }
         
        int max = 0;
        for(int i=1; i<n+1; ++i)
        {
            if(max < arr[i])
                max = arr[i];
        }
        printf("\n%d\n", max);
    }
    return 0;
}

[此贴子已经被作者于2018-5-16 23:55编辑过]

按照你的思路 写了上楼的代码
保持查找树2层
一次最多修改2个节点 很6 很秀
陈独秀你给我坐下

收到的鲜花

• 九转星河 于 2018-05-17 00:22 送鲜花  3朵   附言：好~
• nosnoy 于 2018-05-17 22:02 送鲜花  3朵   附言：我陈独秀就是要皮

我上面也改了点……感觉你写得挺到位了,甚至感觉我还需要参考一下你的,好!~