Cod sursa(job #3218670)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 27 martie 2024 18:12:30
Problema Cuplaj maxim in graf bipartit Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
namespace __template{
    typedef long long ll;
    typedef long double ld;
    typedef pair<ll,ll> pll;
    typedef pair<ld,ld> pld;
    template <typename T>
        using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
};
using namespace __template;
const ll NMAX=2e4+5;
vector<ll> edg[NMAX];
ll c[NMAX];
bool visited[NMAX];
ll fr[2]{};
void dfs(ll u){
    visited[u]=1;
    fr[c[u]]++;
    for(auto it : edg[u]) if(!visited[it]) dfs(it);
}
int main()
{
    freopen("cuplaj.in","r",stdin);
    freopen("cuplaj.out","w",stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,k,ans=0;
    cin>>n>>m>>k;
    for(ll i=0;i<k;i++){
        ll u,v; cin>>u>>v;
        v+=n;
        edg[u].push_back(v);
        edg[v].push_back(u);
        c[v]=1;
    }
    for(ll i=1;i<=n+m;i++){
        if(!visited[i]){
            fr[0]=fr[1]=0;
            dfs(i);
            ans+=max(fr[0],fr[1]);
        }
    }
    cout<<n+m-ans;
    return 0;
}