Codeup 并查集之问题 C: How Many Tables

曾经终败给现在 2023-02-14 02:26 18阅读 0赞

#### 题目翻译： ####

今天是小明的生日。他邀请了很多的朋友。到了吃晚饭的时间，小明想要知道他至少需要多少张桌子。你需要注意并不是小明所有的朋友都互相认识，并且他们都不想自己和陌生人坐在一起。

**这里有一条重要的规定**：如果A认识B，B认识C，这意味着A、B、C互相认识，所以他们可以坐在同一个桌子周围。

**举个例子**：如果告诉你A认识B，B认识C，并且D认识E，因此A、B、C可以呆在一个桌子，D、E可以呆着一个桌子。针对这种情况，小明至少需要2张桌子。

#### 分析： ####

利用并查集求出集合数，输出即可

#include<iostream>
    using namespace std; 
    int father[1010];
    bool isroot[1010];
    int cnt;
    void init()//初始化
    { 
        for(int i=1;i<1010;i++)
        { 
            father[i]=i;
            isroot[i]=false;
        }
        cnt=0;
    }
    int ff(int a)
    { 
        int b=a;
        while(a!=father[a])
        { 
            a=father[a];
        }
        while(b!=father[b])
        { 
            int c=b;
            b=father[b];
            father[c]=a;
        }
        return a;
    }
    void Union(int a,int b)
    { 
        int fa=ff(a);
        int fb=ff(b);
        if(fa!=fb)
        { 
            father[fa]=fb;
        }
    }
    int main()
    { 
        int t;
        cin>>t;
        while(t--)
        { 
            int n,m,a,b;
            cin>>n>>m;
            init();
            for(int i=0;i<m;i++)
            { 
                cin>>a>>b;
                Union(a,b);
            }
            for(int i=1;i<=n;i++)
            { 
                isroot[ff(i)]=true;
            }
            for(int i=1;i<=n;i++)
            { 
                if(isroot[i])cnt++;
            }
            cout<<cnt<<endl;
        }
        return 0;
    }