这里有一个很完美(搞笑但是确实是这样的)翻译
题意
神牛 LXX 昨天刚刚满 18 岁,他现在是个成熟的有为男青年。他有 N 个 MM,分别从 1 到 N 标号。 这些 MM 有些是互相认识的。现在,LXX 为了处理和 MM 们复杂的关系,想把他们划分成尽量多的集合, 要求任意两个属于不同集合的 MM 都必须互相认识。这样方便交流。现在 LXX 想知道最多可以分成多 少个集合,每个集合的人数是多少。
输入输出样例
7 16 1 3 1 4 1 5 2 3 3 4 4 5 4 7 4 6 5 6 6 7 2 4 2 7 2 5 3 5 3 7 1 7
3 1 2 4
这题可以BFS过
比较好的一道题
但是因为我太菜了打不来,还是看题解的
我用vector存边
向大佬学了一下iterator(其实没学会)
代码
#include<bits/stdc++.h> #define ll long long #define N 100005 using namespace std; vector<ll>G[N]; ll q[N],st[N],num[N],mark[N]; int main() { ll n,m;scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) { ll x,y;scanf("%lld%lld",&x,&y); G[x].push_back(y); G[y].push_back(x); } for(ll i=1;i<=n;i++) q[i]=i; ll top=n,ans=0,cnt=0,nt=0; while(top){ ans++; cnt++; st[nt=1]=q[top--]; while(nt){ num[ans]++; ll x=st[nt--]; cnt++; for(vector<ll>::iterator i=G[x].begin();i != G[x].end();++i) mark[*i]=cnt; ll top0=top; top=0; for(ll i=1;i<=top0;i++){ int x=q[i]; if(mark[x]!=cnt) st[++nt]=x; else q[++top]=x; } } } printf("%lld ",ans); sort(num+1,num+1+ans); for(ll i=1;i<=ans;i++) printf("%lld ",num[i]); return 0; }