2 条题解

  • 1
    @ 2023-2-21 22:18:57
    #include <bits/stdc++.h>
    #define ll long long
    #define N 500010
    using namespace std;
    int fa[N],ans[N];
    int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}//查找所在集合(fa)
    int main()
    {
    	int n,i,k,j,t,m,lst;
        cin>>n>>m;
    	for (i=1;i<=n;i++) fa[i]=i;//初始化
    	for (i=1;i<=m;i++)
    	{
    		cin>>k;
            if (k==0) continue;//如果输入是0就直接continue
    		cin>>t;lst=t;
    		for (j=2;j<=k;j++)
    		{
    			cin>>t;int a=find(lst),b=find(t);
    			fa[a]=b;//合并
    		}
    	}
    	for (i=1;i<=n;i++) ans[find(i)]++;for (i=1;i<=n;i++) cout<<ans[find(i)]<<' ';//输出
        return 0;
    }
    
    • 0
      @ 2022-7-14 15:20:01

      并查集直接维护集合关系

      jfMZTS.png

      • 1

      信息

      ID
      1914
      时间
      1000ms
      内存
      256MiB
      难度
      2
      标签
      递交数
      41
      已通过
      27
      上传者