TJ 交流问题 —> 黑白染色问题

看完题目标签，一个并查集，一个深搜，有点无法理解

看完题目感觉深搜思路很好想 不知道怎么写并查集

其实就是有交流的两人是不同学校，直接建图深搜交替染色，统计连通分量中黑 or 白的最大值，最小值相加即可

#include <iostream>
#include <vector>
using namespace std;
const int N=1e5+5;
int n,m,w,b;
vector<int> g[N];
bool vis[N],col[N];
void dfs(int u){
    vis[u]=1;
    col[u] ? b++ : w++;
    for(int v:g[u]){
        if(!vis[v]){
            col[v]=col[u]^1;
            dfs(v);
        }
    }
    return;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int mn=0,mx=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            col[i]=0;
            w=b=0;
            dfs(i);
            mn+=min(w,b);
            mx+=max(w,b);
        }
    }
    cout << mn << ' ' << mx;
    return 0;
}

为什么都在写广搜？