题目

分析

我们抽象的认为一些不能互相辨认的人，被分到了一个集合，每当又有一场演出，就将每个出演的演员扔出集合，再将上次在相同集合的分在同一集合。
然后修改被分的集合和被新创建的时间，当集合只有一个数的时候不可再分。
输出每个演员所在的集合的最后修改时间，仅当该演员所在的集合中只有一个演员。

#include <cmath>#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <queue>const int maxlongint=2147483647;const int mo=1000000007;const int N=100005;using namespace std;int fa[N*20],tot,t[N*20],n,m,a[N],bz[N*20],d[N],num,sum[N];int main(){ ???scanf("%d%d",&n,&m); ???sum[0]=n; ???for(int i=1;i<=m;i++) ???{ ???????int k; ???????scanf("%d",&k); ???????num=0; ???????for(int j=1;j<=k;j++) ???????{ ???????????scanf("%d",&a[j]); ???????????if(sum[fa[a[j]]]!=1 || bz[fa[a[j]]]) ???????????{ ???????????????if(!bz[fa[a[j]]]) ???????????????{ ???????????????????t[fa[a[j]]]=i; ???????????????????d[++num]=fa[a[j]]; ???????????????????????sum[fa[a[j]]]--; ???????????????????bz[fa[a[j]]]=++tot; ???????????????????fa[a[j]]=tot; ???????????????????t[tot]=i; ???????????????????sum[tot]=1; ???????????????} ???????????????else ???????????????sum[fa[a[j]]]--,fa[a[j]]=bz[fa[a[j]]],sum[fa[a[j]]]++; ???????????} ???????} ???????for(int j=1;j<=num;j++) ????????????bz[d[j]]=0; ???} ???for(int i=1;i<=n;i++) ????????if(sum[fa[i]]==1) ???????????printf("%d ",t[fa[i]]); ???????else printf("0 ");}

【JSOI2014】歌剧表演

原文地址：https://www.cnblogs.com/chen1352/p/9071406.html