dtcms模板 后台视频教程 前端视频教程 后台模板
Python读写CSV文件
递归找出文件夹下所有的.java文件(Java)
良心帖!看完这篇,你的Python入门基础就差不多了!(内含资料试听)
Ubuntu换国内源
1062 最简分数 (20分) - PAT (Basic Level) Practice (中文)
画图学 JVM(九)08 堆
使用node中的net模块简单实现网络编程中的消息群发
golang 学习文档 第一阶段学习总结
ASP.Net学习(三)
【算法与数据结构-1】时间复杂度-以斐波拉切为例子
2019/7/21 21:26:21 人评论 次浏览 分类:学习教程
题意
大概就是分成几个小团体,给每个人用1 - n编号,当对某个人传播消息的时候,整个小团体就知道这个消息,输出 分别对1 - n编号的某个人传递消息时,有多少人知道这个消息。
Input
第一行n和m(n,m<=5*10^5) 接着m行,每行一个ki,接着ki(0<=ki<=n)个数,代表这个ki个人在一个QQ群里
Output
输出n个数,第i个代表,第ai个人知道谣言后,最多可以传播给几个人
Example
Input 7 5 3 2 5 4 0 2 1 2 1 1 2 6 7
7 5 3 2 5 4 0 2 1 2 1 1 2 6 7
Output 4 4 1 4 4 2 2
4 4 1 4 4 2 2
#include #include #include #include #include #include #include #include #include <string> #include #include #include #include <set> #include #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 100005*5 using namespace std; int par[Maxn];//par[i] i的根 int sum[Maxn];//sum[i] i集合的个数 int n,m,k; int findr(int x)//查询根 { if(par[x]==x) return x; else return par[x]=findr(par[x]); } void unite(int x,int y) { x=findr(x);//查x,y根 y=findr(y); if(x==y)//根相同不用管 return; par[y]=x;//若根不同,y并入x,则y的根为x,同理x也能并入y 这里随意 sum[x]+=sum[y];//y并入x,则x的集合个数等于x集合个数+y集合个数 } int main() { cin>>n>>m; for(int i=1;i<=n;i++) { par[i]=i; sum[i]=1; } while(m--) { cin>>k; int a,b; if(k>0) { //用第一个数与后面的书比较即可 cin>>a; for(int i=1;i) { cin>>b; unite(a,b); } } } for(int i=1;i<=n;i++) { int x=findr(i);//查根,输出这个根的集合个数 cout<" "; } cout<<endl; return 0; }
上一篇:配一副适合程序员的眼镜
下一篇:hadoop的java.lang.InterruptedException