ARC111-B Reversible Cards

これは解けないとダメなやつだった

https://atcoder.jp/contests/arc111/tasks/arc111_b

問題概要

N枚のカードがあり、ある面にはA[i] , その裏面にはB[i]が書かれている。N枚のカードの裏表を自由に選択できる時、表を向いている数の種類は最大で何種類？

• 1 ≤ N ≤ 200,000
• 1 ≤ A_i ,B_i ≤ 400,000

解法

• maxflowの計算量的にフローはダメだろうと思っていたが、どうもうまくやるとできたらしい。とりあえず、典型としてグラフを構成する。

• A_iとB_iの間に辺を張り、無向グラフを構成する（流石に初見じゃない）

• こうして構成されたグラフにおいて、カード(A[i] , B[i])のうちどちらかを表にすることは、Edge(A[i] , B[i])において、一方の頂点を色塗ることに対応していて、構成された連結成分が木ならばサイズ-1だけ、木ではないならば全部の頂点を色付けることができる。 類題が思い出せないけどABCとか企業ARCで去年あたり2、3回見た記憶がある...

• ところで、この方法だとサイズが1の時だけ例外になる。これも含めて計算できる方法もあるのかな

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

#define LIM 400010

int N;
vector<int> graph[LIM];
int visited[LIM];

int component_size = 0;
bool istree;
void dfs(int x,int pre){
    component_size++;
    visited[x] = 1;
    for(auto e : graph[x]){
        if(e != pre){
            if(visited[e]){
                istree = false;
            }else{
                dfs(e,x);
            }
        }
    }
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a,b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int ans = 0;
    for (int i = 0; i < LIM; i++) {
        if(graph[i].size() && !visited[i]){
            component_size = 0;
            istree = true;
            dfs(i , -1);
            if(istree && (component_size != 1)){
                ans += component_size - 1;
            }else{
                ans += component_size;
            }
        }
    }
    
    cout << ans << '\n';
    
}