Source Code
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair <int,int>
#define F first
#define S second
#define ever (;;)

const int N = 100100;

int n,m,k,freq[N],num,ans,cum[N],mx,Get[N];
vector <int> vr[N],vl[N],v;
map <ii,int> mp;
multiset <int> s;

int main()
{
    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=k;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);

        vl[a].push_back(b);
        vr[b].push_back(a);
        freq[a]++;
    }

    for(int i=1;i<=n;i++)
    {
        if( freq[i] == 2 )
        {
            int x = vl[i][0];
            int y = vl[i][1];

            mp[ { x , y } ]++;
            mp[ { y , x } ]++;
        }
    }

    for(int i=1;i<=n;i++)
        num += ( freq[i] >= 1 );

    ans = num;

    for(int i=1;i<=m;i++)
    {
        for(auto &x:vr[i])
            Get[i] += ( freq[x] == 1 );

        ans = min( ans , num+1-Get[i] );
        s.insert(Get[i]);
    }

    for(auto &X:mp)
    {
        int x = X.F.F;
        int y = X.F.S;
        int c = X.S;

        ans = min( ans , num+2 - c - Get[x] - Get[y] );
    }

    if( m >= 2 )
    {
        int x = *s.rbegin();
        s.erase(s.find(x));
        int y = *s.rbegin();
        s.erase(s.find(y));

        ans = min( ans , num+2-x-y);
    }

    printf("%d\n",ans);
}
Copy
Min Vertex Cover 2 Naseem17
GNU G++17
195 ms
17.5 MB
Accepted