题意:
![ARC111 B - Reversible Cards(思维+树的判断) ARC111 B - Reversible Cards(思维+树的判断)](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPTIwMjEwMTE5MTYxMTQ0MjQ2LnBuZz8sdHlwZV9abUZ1WjNwb1pXNW5hR1ZwZEdrLHNoYWRvd18xMCx0ZXh0X2FIUjBjSE02THk5aWJHOW5MbU56Wkc0dWJtVjBMM2RsYVhocGJsODBOREUzT0Rjek5nPT0sc2l6ZV8xNixjb2xvcl9GRkZGRkYsdF83MA==)
解法:
将(ai,bi)视为ai和bi之间有一条边,
那么对于图中的所有连通块:
1.如果连通块是一棵cnt个点的树,那么一定能选出cnt-1个点.
2.如果连通块是cnt个点的非树连通图,那么一定能选出cnt个点.
因此问题变为判断每个连通块是否是树,dfs一下就行了.
code:
#include <bits/stdc++.h>
using namespace std;
#define PI pair<int,int>
const int maxm=4e5+5;
vector<PI>g[maxm];
int mark[maxm];
int is[maxm];
int isTree,cnt;
int n;
void dfs(int x,int e){//e是父节点到当前点的边的编号
mark[x]=1;
cnt++;
for(auto i:g[x]){
int v=i.first,ee=i.second;
if(ee==e)continue;
if(!mark[v]){
dfs(v,ee);
}else{
isTree=0;
}
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
is[a]=is[b]=1;
g[a].push_back({b,i});
g[b].push_back({a,i});
}
int ans=0;
for(int i=1;i<=4e5;i++){
if(is[i]&&!mark[i]){
isTree=1,cnt=0;
dfs(i,-1);
if(isTree)ans+=cnt-1;
else ans+=cnt;
}
}
cout<<ans<<endl;
return 0;
}