Educational Codeforces Round 37 (Rated for Div. 2) 920E E. Connected Components?

题

　　OvO http://codeforces.com/contest/920/problem/E

解

　　模拟一遍……

　　1.首先把所有数放到一个集合 s 中，并创建一个队列 que

　　2.然后每次随便取一个数，并且从集合中删除这个数，将这个数放入 que

　　3.取 que 首元素，记为 now，然后枚举集合 s，每次找到 s 中和 now 相连的元素 x，从 s 中删除元素 x，并且把 x 放入 que 中。

　　4.如果 s 不为空，回到步骤2

　　可见就是一个模拟，至于复杂度，计算如下。

　　由于每个数字只会从集合 s 中删除一次。步骤3中枚举集合 s 元素的操作中，记成功从集合 s 中删除元素的为有效操作，反之为无效操作，则每一次有效操作必然会使 s 中元素数量减，所以有效操作复杂度为O(n)。而每次无效操作则必然会使用到一对题目所给的 (x,y)，其中 x 与 y 不相连，可见无效操作复杂度为 O(m)。

　　其他复杂度计算显然。加起来不会超时。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <queue>

 using namespace std;

 const int M=2e5+;

 const int N=2e5;

 vector<int> mp[M];

 queue<int> que;

 set<int> s;

 int n,m;

 int lans,ans[M];

 void init()

 {

     for(int i=;i<=N;i++)

         mp[i].clear();

     s.clear();

     lans=;

 }

 bool isConnected(int a,int b)

 {

     vector<int>::iterator it=lower_bound(mp[a].begin(),mp[a].end(),b);

     if(it==mp[a].end() || *it!=b) return true;

     return false;

 }

 void solve()

 {

     queue<int> dlt;

     int now,tmp;

     set<int>::iterator it,tmp_it;

     for(int i=;i<=n;i++)

         s.insert(i);

     while(s.size()>)

     {

         while(!que.empty()) que.pop();

         while(!dlt.empty()) dlt.pop();

         lans++; ans[lans]=;

         it=s.begin(); now=*it;

 //        cout<<now<<' ';

         s.erase(it); ans[lans]++;

         que.push(now);

         while(!que.empty())

         {

             now=que.front(); que.pop();

             for(it=s.begin();it!=s.end();it++)

                 if(isConnected(now,*it))

                 {

 //                    cout<<*it<<' ';

                     que.push(*it),ans[lans]++,dlt.push(*it);

                 }

             while(!dlt.empty())

             {

                 tmp=dlt.front(); dlt.pop();

                 s.erase(tmp);

             }

         }

 //        cout<<endl;

 //        cout<<s.size()<<endl;

     }

 }

 int main()

 {

     init();

     int a,b;

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&a,&b);

         mp[a].push_back(b),mp[b].push_back(a);

     }

     for(int i=;i<=n;i++)

         sort(mp[i].begin(),mp[i].end());

     solve();

     sort(ans+,ans+lans+);

     printf("%d\n",lans);

     for(int i=;i<=lans;i++)

         printf("%d ",ans[i]);

     puts("");

     return ;

 }

巴特西

Educational Codeforces Round 37 (Rated for Div. 2) 920E E. Connected Components?

最新文章

热门文章