并查集 Hdu 1272 (判环)+ Hdu 1213 + Hdu 1232 + Hdu 3172

我不是女神ヾ 2022-09-20 15:09 129阅读 0赞

**Hdu 1272 小希的迷宫**

思路：两点的根节点相同，并且他们又彼此连通，则说明构成环。如果无环且 点数-1==边数 则说明只有一个连通块

#include <cstdio>
    #include <cstring>
    
    const int MAX=100005;
    
    bool visit[MAX];
    
    class Disjoint_Set
    {
    public:
    	int father[MAX];            /*father[x]表示x的父节点*/
    	int rank[MAX];              //以该节点为根节点的点数,同时起到按秩合并的作用
    
    	void Init (int n)
    	{
    		for (int i=0;i<=n;i++)
    			Make_Set (i);
    	}
    
    	void Make_Set (int x)
    	{
    		father[x]=x;
    		rank[x]=1;
    	}
    
    	int Find_Set (int x)
    	{
    		if (x != father[x])
    			father[x] = Find_Set(father[x]);//回溯
    		return father[x];
    	}
    
    	bool Union (int x,int y)
    	{//返回false表示要合并的两点已在同一个集合中
    		int a=Find_Set (x);
    		int b=Find_Set (y);
    		if (a == b)
    			return false;
    		if (rank[a] >= rank[b])
    		{
    			father[b]=a;
    			rank[a]+=rank[b];
    		}
    		else
    		{
    			father[a]=b;
    			rank[b]+=rank[a];
    		}
    		return true;
    	}
    }ob;
    
    int main ()
    {
    	int n,m;
    	while (~scanf("%d%d",&n,&m),n!=-1 && m!=-1)
        {
            if (n==0 && m==0)
            {
                printf("Yes\n");
                continue;
            }
    		ob.Init(MAX);
    		memset(visit,false,sizeof(visit));
    		visit[n]=visit[m]=true;
    		ob.Union(n,m);
    		int cnt=1;   //已经有一条边
    		int tmp=2;   //已经有2个点
    		bool flag=true;
    		while(scanf("%d%d",&n,&m),n||m)
            {
                cnt++;
                if (visit[n]==false)
                {
                    visit[n]=true;
                    tmp++;
                }
                if (visit[m]==false)
                {
                    visit[m]=true;
                    tmp++;
                }
                if (ob.Union(n,m)==false)
                    flag=false;  //若n和m的根节点相同，并且他们又彼此连通，则说明构成环
            }
    		if (flag && cnt==tmp-1) //无环,且所有点连通
                printf("Yes\n");
            else
                printf("No\n");
    	}
    	return 0;
    }

**Hdu 1213 How Many Tables**

题意：有n个人参加的party，要准备多少张桌子，使得任意桌子上坐的人都是相互认识的。求最少要准备的桌子的数量。

#include <cstdio>
    
    const int MAX=1005;
    
    class Disjoint_Set
    {
    public:
    	int father[MAX];            /*father[x]表示x的父节点*/
    	int rank[MAX];              //以该节点为根节点的点数,同时起到按秩合并的作用
    
    	void Init (int n)
    	{
    		for (int i=0;i<=n;i++)
    			Make_Set (i);
    	}
    
    	void Make_Set (int x)
    	{
    		father[x]=x;
    		rank[x]=1;
    	}
    
    	int Find_Set (int x)
    	{
    		if (x != father[x])
    			father[x] = Find_Set(father[x]);//回溯
    		return father[x];
    	}
    
    	void Union (int x,int y)
    	{
    		int a=Find_Set (x);
    		int b=Find_Set (y);
    		if (a == b)
    			return;
    		if (rank[a] >= rank[b])
    		{
    			father[b]=a;
    			rank[a]+=rank[b];
    		}
    		else
    		{
    			father[a]=b;
    			rank[b]+=rank[a];
    		}
    	}
    }ob;
    
    int main ()
    {
    	int T,n,m;
    	scanf("%d",&T);
    	while (T--)
        {
            scanf("%d%d",&n,&m);
    		ob.Init(n);
    		int a,b,ans=0,i;
    		for (i=1;i<=m;i++)
    		{
    			scanf("%d%d",&a,&b);
                ob.Union(a,b);
    		}
    		for (i=1;i<=n;i++)
                if (ob.father[i]==i)
                    ans++;
    		printf("%d\n",ans);
    	}
    	return 0;
    }

**Hdu 1232 畅通工程**

#include <cstdio>
    
    const int MAX=1005;
    
    class Disjoint_Set
    {
    public:
    	int father[MAX];
    	int rank[MAX];              //以该节点为根节点的点数,同时起到按秩合并的作用
    
    	void Init (int n)
    	{
    		for (int i=0;i<=n;i++)
    			Make_Set (i);
    	}
    
    	void Make_Set (int x)
    	{
    		father[x]=x;
    		rank[x]=1;
    	}
    
    	int Find_Set (int x)
    	{
    		if (x != father[x])
    			father[x] = Find_Set(father[x]);//回溯
    		return father[x];
    	}
    
    	void Union (int x,int y)
    	{
    		int a=Find_Set (x);
    		int b=Find_Set (y);
    		if (a == b)
    			return;
    		if (rank[a] >= rank[b])
    		{
    			father[b]=a;
    			rank[a]+=rank[b];
    		}
    		else
    		{
    			father[a]=b;
    			rank[b]+=rank[a];
    		}
    	}
    }ob;
    
    int main ()
    {
    	int n,m;
    	while (~scanf("%d%d",&n,&m),n)
           {
    		ob.Init(n);
    		int a,b,ans=0,i;
    		for (i=1;i<=m;i++)
    		{
    			scanf("%d%d",&a,&b);
                ob.Union(a,b);
    		}
    		for (i=1;i<=n;i++)
                if (ob.father[i]==i)
                    ans++;
    		printf("%d\n",ans-1);
    	}
    	return 0;
    }

**Hdu 3172 Virtual Friends**

给出m条交友信息，每一句含两个人名，表示两个人成为朋友，求是这两个人朋友的有多少个人(含自己)

时间卡的比较严,名字不要用STL的string,用map映射时间还是可以接受的

输入格式很坑爹

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <map>
    using namespace std;
    
    const int MAX=100005;
    
    class Disjoint_Set
    {
    public:
    	int father[MAX];            /*father[x]表示x的父节点*/
    	int rank[MAX];              //以该节点为根节点的点数,同时起到按秩合并的作用
    
    	void Init (int n)
    	{
    		for (int i=0;i<=n;i++)
    			Make_Set (i);
    	}
    
    	void Make_Set (int x)
    	{
    		father[x]=x;
    		rank[x]=1;
    	}
    
    	int Find_Set (int x)
    	{
    		if (x != father[x])
    			father[x] = Find_Set(father[x]);//回溯
    		return father[x];
    	}
    
    	void Union (int x,int y)
    	{
    		int a=Find_Set (x);
    		int b=Find_Set (y);
    		if (a == b)
    			return;
    		if (rank[a] >= rank[b])
    		{
    			father[b]=a;
    			rank[a]+=rank[b];
    		}
    		else
    		{
    			father[a]=b;
    			rank[b]+=rank[a];
    		}
    	}
    }ob;
    
    int main ()
    {
    	int T,n;
    	while (~scanf("%d",&T))
    	while (T--)
        {
            scanf("%d",&n);
    		ob.Init(MAX);
    		int id=1;
    		char str[25],ch[25];
    		map<string,int> m;
    		for (int i=1;i<=n;i++)
    		{
    			scanf("%s%s",str,ch);
    			if (m[str]==0)
                    m[str]=id++;
                if (m[ch]==0)
                    m[ch]=id++;
                int a=m[str];
                int b=m[ch];
                ob.Union(a,b);
                printf("%d\n",ob.rank[ ob.Find_Set(m[str]) ]);
    		}
    	}
    	return 0;
    }