Advertisement

# 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