并查集求助!!!5、8、9、10 WA
  • 板块P2835 刻录光盘
  • 楼主qzhw
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/3/1 19:54
  • 上次更新2023/10/28 07:28:24
查看原帖
并查集求助!!!5、8、9、10 WA
397574
qzhw楼主2022/3/1 19:54

传送门

测试点

//注:4到30行都是快读快写 
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t)
{
    t=0;
    register char ch=getchar();
    while(!('0'<=ch&&ch<='9'))
{
        if(ch=='-') t*=-1;
        ch=getchar();
    }
    while(('0'<=ch&&ch<='9'))
{
        t=((t<<1)+(t<<3))+ch-'0';
        ch=getchar();
    }
}
template <typename T,typename... Args> inline void read(T& t, Args&... args)
{
    read(t);read(args...);
}
template <typename T>inline void write(T x)
{
    if(x<0) putchar('-'),x=~(x-1);
    int s[40],top=0;
    while(x) s[++top]=x%10,x/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}//快读快写
int k,n,m,sum,father[205];
void init()
{
	for(register int i=1;i<=n;i++)
	father[i]=i;
}
int find(int x)//找父亲 
{
	return x==father[x]?x:father[x]=find(father[x]);
}
void lian(int x,int y)//连接2点 
{
	x=find(x); y=find(y);father[y]=x;
}
bool pd(int x,int y)//判断是否在同一集合 
{
	if(find(x)==find(y))
	return 1;
	return 0;
}
int main()
{
	read(n);
	init();
	for(register int i=1;i<=n;i++)
	{
		k=-1;
		while(k!=0)
		{
			read(k);
			if(!pd(i,k)&&k!=0&&father[k]==k)
			lian(i,k);
		}
	}
	for(register int i=1;i<=n;i++)
	if(father[i]==i)
	sum++;
	write(sum);
	return 0;
}
2022/3/1 19:54
加载中...