Advertisement
RaFiN_

codeforces -242-D

Dec 29th, 2018
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 KB | None | 0 0
  1. /* Whenever no of edges is <= 1e6 then if we insert all nodes in a set and each node is accessed exactly once then the loop below runs exactly o(2*m) times ... because all edges are accessed by two of it's connecting nodes exactly two times...... */
  2.  
  3. int main()
  4. {
  5.     booster()
  6.     ///read("input.txt");
  7.  
  8.     int n,m;cin>>n>>m;
  9.     for(int i = 1;i<=m;i++)
  10.     {
  11.         int a,b;
  12.         cin>>a>>b;
  13.         v[a].pb(b);
  14.         v[b].pb(a);
  15.     }
  16.     set<int>s;
  17.     vi ans;
  18.     for(int i = 1;i<=n;i++)
  19.     {
  20.         cin>>arr[i];
  21.         if(arr[i]==0)s.insert(i);
  22.     }
  23.  
  24.     while(!s.empty())
  25.     {
  26.         int x = *s.begin();
  27.         s.erase(x);
  28.         if(cnt[x]!=arr[x])continue;
  29.         cnt[x]++;
  30.         ans.pb(x);
  31.         for(auto it : v[x])
  32.         {
  33.             cnt[it]++;
  34.             if(arr[it]==cnt[it])s.insert(it);
  35.         }
  36.     }
  37.  
  38.     cout<<ans.size()<<endl;
  39.  
  40.     for(auto it : ans)cout<<it<<" ";
  41.  
  42.  
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement