SHARE
TWEET

Untitled

a guest Jun 9th, 2019 30 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int visited[2000090];
  5. vector<int>edges[2000090];
  6. vector<int>ans;
  7. int n;    
  8. void bfs(int start)
  9. {
  10.     int tok=1;
  11.     vector<pair<int,int>>que;
  12.     int index=0;
  13.     que.push_back(make_pair(start,1));
  14.     visited[start]++;
  15.     ans.push_back(start);
  16.     int last_index=0;
  17.     while(index!=n)
  18.     {
  19.         while(index<=last_index)
  20.         {
  21.             int s=que[index].first;
  22.             for(auto x:edges[s]){
  23.                 if(visited[x]==0){
  24.                     // cout<<"check "<<s<<" "<<x<<endl;
  25.                     if(!tok){
  26.                         ans.push_back(x);
  27.                     }
  28.                     visited[x]=1;
  29.                     que.push_back(make_pair(x,tok^1));
  30.                 }
  31.             }
  32.             index++;
  33.         }
  34.         last_index=que.size()-1;
  35.         tok^=1;
  36.     }
  37. }
  38. main()
  39. {
  40.     int q;
  41.     cin>>q;
  42.     while(q--){
  43.         ans.clear();
  44.         int m;
  45.         cin>>n>>m;
  46.         vector<pair<int,int> >degree;
  47.         for(int i=1;i<=n;i++){
  48.             edges[i].clear();
  49.             degree.push_back(make_pair(0,i));
  50.         }
  51.         for(int i=0;i<m;i++){
  52.             int u,v;
  53.             cin>>u>>v;
  54.             degree[u].first++;
  55.             degree[v].first++;
  56.             edges[u].push_back(v);
  57.             edges[v].push_back(u);
  58.         }
  59.         // cout<<"edges\n";
  60.         // for(int i=1;i<=n;i++)
  61.         // {
  62.         //     cout<<"i="<<i<<endl;
  63.         //     for(auto x:edges[i]){
  64.         //         cout<<x<<" ";
  65.         //     }
  66.         //     cout<<endl;
  67.         // }
  68.         memset(visited,0,sizeof(visited));
  69.         sort(degree.begin(),degree.end());
  70.         int start=degree[degree.size()-1].second;
  71.         // cout<<start<<endl;
  72.         bfs(start);
  73.         // cout<<"ans\n";
  74.         cout<<ans.size()<<endl;
  75.         for(auto x:ans){
  76.             cout<<x<<" ";
  77.         }
  78.         cout<<endl;
  79.     }
  80. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top