卖货小程序,青岛seo经理,ui设计培训机构好,数字广东网络建设有限公司题干#xff1a;
无向图中给定n个顶点#xff0c;m条不存在的边(除了这m条边#xff0c;其余都存在)#xff0c;求图的连通分量#xff0c;及每个连通分量的大小。
解题报告#xff1a;
https://codeforces.com/blog/entry/4556 AC代码#xff1a;
#includecstd…题干
无向图中给定n个顶点m条不存在的边(除了这m条边其余都存在)求图的连通分量及每个连通分量的大小。
解题报告
https://codeforces.com/blog/entry/4556 AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includeunordered_map
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 5e5 5;
unordered_mapint,bool mp[MAX];
vectorint vv;
vectorvectorint ans;
vectorint bfs(int x) {vectorint res;queueint q;q.push(x);while(q.size()) {int cur q.front();q.pop();res.pb(cur);
// int up vv.size();这里不能这样写因为size是动态的。for(int i 0; i(int)vv.size(); i) {int v vv[i];if(mp[cur].count(v) 0) {swap(vv[i],vv.back());//用来实现set的erase操作减少常数。 vv.pop_back();//用来实现set的erase操作 i--;q.push(v);}}}return res;
}
int main()
{int n,m;cinnm;for(int i 1; in; i) vv.pb(i);for(int x,y,i 1; im; i) {scanf(%d%d,x,y);mp[x][y]1;mp[y][x]1;}while(!vv.empty()) {int v vv.back();vv.pop_back();vectorint cnt bfs(v);ans.push_back(cnt);}sort(ans.begin(),ans.end());printf(%d\n,ans.size());for(int i 0; i(int)ans.size(); i) {printf(%d ,ans[i].size());for(int j 0; j(int)ans[i].size(); j) {printf(%d ,ans[i][j]);}printf(\n);}return 0 ;
}
