这里有一个很完美（搞笑但是确实是这样的）翻译

题意

神牛 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\n",ans); sort(num+1,num+1+ans); for(ll i=1;i<=ans;i++) printf("%lld ",num[i]); return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/9881949.html

相关资源：poi-ooxml-3.7-20101029.jar