305348: CF1012B. Chemical table
Memory Limit:512 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Chemical table
题意翻译
给你一个n*m的矩形,一开始有q个格子上被标记。对于任意两行两列,如果交汇的四个格子中有三个被标记,那么第4个会被自动标记。问你至少需要手动标记几个格子,使得整个矩形内的格子都被标记。题目描述
Innopolis University scientists continue to investigate the periodic table. There are $ n·m $ known elements and they form a periodic table: a rectangle with $ n $ rows and $ m $ columns. Each element can be described by its coordinates $ (r,c) $ ( $ 1<=r<=n $ , $ 1<=c<=m $ ) in the table. Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions $ (r_{1},c_{1}) $ , $ (r_{1},c_{2}) $ , $ (r_{2},c_{1}) $ , where $ r_{1}≠r_{2} $ and $ c_{1}≠c_{2} $ , then we can produce element $ (r_{2},c_{2}) $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1012B/a1ec2b34980f17dea8ef9d5c32f5d591ae712bba.png)Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions. Innopolis University scientists already have samples of $ q $ elements. They want to obtain samples of all $ n·m $ elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ , $ q $ ( $ 1<=n,m<=200000 $ ; $ 0<=q<=min(n·m,200000) $ ), the chemical table dimensions and the number of elements scientists already have. The following $ q $ lines contain two integers $ r_{i} $ , $ c_{i} $ ( $ 1<=r_{i}<=n $ , $ 1<=c_{i}<=m $ ), each describes an element that scientists already have. All elements in the input are different.
输出格式
Print the minimal number of elements to be purchased.
输入输出样例
输入样例 #1
2 2 3
1 2
2 2
2 1
输出样例 #1
0
输入样例 #2
1 5 3
1 3
1 1
1 5
输出样例 #2
2
输入样例 #3
4 3 6
1 2
1 3
2 2
2 3
3 1
3 3
输出样例 #3
1