Advertisement
ekanshlohiya98

Vertex cover (approx)

Jun 25th, 2022
681
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //vertex cover approximate algorithm
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  6. typedef long double ld;
  7. #define pb push_back
  8. #define mp make_pair
  9. #define vpll vector<pair<ll,ll>>
  10. #define vll vector<ll>
  11. #define mpll map<ll,ll>
  12. #define all(x) x.begin(),x.end()
  13. #define sortall(x) sort(x.begin(),x.end())
  14. #define line cout<<'\n'
  15. #define fo(i,n) for(int i=0;i<n;i++)
  16. #define foe(i,a,n) for(int i=a;i<n;i++)
  17. #define fr(i,n) for(int i=n-1;i>=0;i--)
  18. #define cy cout<<"YES"<<endl
  19. #define cn cout<<"NO"<<endl
  20. #define debug(x) cout<<x<<endl
  21. #define print(x) cout<<x<<" "
  22. #define deb(x,y) cout<<x<<" "<<y<<endl
  23. #define MOD 1000000007
  24. const int N1=100001;
  25. bool isPrime[N1];
  26. void sieve()
  27. {
  28.     memset(isPrime, true, sizeof(isPrime));
  29.     for (int p = 2; p * p <= N1; p++)
  30.     {
  31.         if (isPrime[p] == true)
  32.         {
  33.             for (int i = p * p; i <= N1; i += p)
  34.                 isPrime[i] = false;
  35.         }
  36.     }
  37. }
  38. long long power(long long a, long long b) {
  39.     if (b == 0)
  40.         return 1;
  41.     long long res = power(a, b / 2);
  42.     if (b % 2)
  43.         return res * res * a;
  44.     else
  45.         return res * res;
  46. }
  47. /*====================================================================================*/
  48.  
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(false);
  52.     cin.tie(NULL);
  53.     ll t=1;
  54.     cin>>t;
  55.  
  56.     while(t--)
  57.     {
  58.         ll n,m; cin>>n>>m;
  59.         vector<vector<int>> edges;
  60.         for(int i=0;i<m;i++)
  61.         {
  62.             int u,v; cin>>u>>v;
  63.             edges.push_back({u,v});
  64.         }
  65.         vector<int> ans;
  66.         while(edges.size()>0)
  67.         {
  68.             vector<int> v=edges[0];
  69.             ans.push_back(v[0]); ans.push_back(v[1]);
  70.             for(int i=0;i<edges.size();){
  71.                 if(edges[i][0]==v[0] or edges[i][1]==v[0] or edges[i][0]==v[1] or edges[i][1]==v[1]){
  72.                     edges.erase(edges.begin()+i);
  73.                 }
  74.                 else i++;
  75.             }
  76.         }
  77.         for(auto it:ans) print(it);
  78.         line;
  79.     }
  80. }
  81.  
Advertisement
RAW Paste Data Copied
Advertisement