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

const int N = 100010;

int n , m , k;

int cur[N];

vector< int > g[N];
vector< int > g2[N];

vector< int > v;

int frq[N] , now[N];

int mx1 = 0 , mx2 = 0;


int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int l , r , i = 0 ;i < k;i++){
        scanf("%d%d",&l,&r);
        g[r].push_back(l);
        g2[l].push_back(r);
        cur[l]++;
    }

    for(int i = 1;i <= m;i++){
        for(int j = 0 ;j < (int)g[i].size();j++){
            if(cur[g[i][j]] == 1)
                now[i]++;
        }
        if(now[i] > mx1){
            mx2 = mx1;
            mx1 = now[i];
        }
        else if(now[i] > mx2){
            mx2 = now[i];
        }
    }
    int a = 0;
    for(int i = 1;i <= n;i++) if(cur[i] > 0) a++;
    int ans = a;

    for(int mx , tmpNode , i = 1;i <= m;i++){
        ans = min(ans , a - now[i] + 1);
        if(mx1 == now[i])
            mx = mx2;
        else
            mx = mx1;
        for(int j = 0 ;j < (int)g[i].size();j++){
            if(cur[g[i][j]] == 2){
                tmpNode = g[i][j];
                for(int k = 0 ;k < (int)g2[tmpNode].size();k++){
                    if(g2[tmpNode][k] == i) continue;
                    tmpNode = g2[tmpNode][k];
                    break;
                }
                now[tmpNode]++;
                mx = max(mx , now[tmpNode]);
                v.push_back(tmpNode);
            }
        }
        ans = min(ans , a - now[i] - mx + 2);
        while((int)v.size() > 0){
            now[v.back()]--;
            v.pop_back();
        }
    }
    cout << ans << endl;

}
Copy
Min Vertex Cover 2 Kilani
GNU G++17
151 ms
10.4 MB
Accepted