题目链接
https://www.luogu.org/problemnew/show/P2860
思路
缩点，之后就成了个树一般的东西了
然后（叶子节点+1）/2就是答案，好像贪心的样子，lmc好像讲过诶
#include <iostream>
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#define iter vector<int>::iterator
using namespace std;
const int N=1e5+7;
int read() {
int x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m;
vector<int> G[N];
int dfn[N],low[N],SD,stak[N],top,vis[N],belong[N];
void tarjan(int u,int fa) {
dfn[u]=low[u]=++SD;
vis[u]=1;
stak[++top]=u;
for(iter it=G[u].begin();it!=G[u].end();++it) {
if(*it==fa) continue;
if(!dfn[*it]) {
tarjan(*it,u);
low[u]=min(low[u],low[*it]);
} else if(vis[*it])
low[u]=min(low[u],dfn[*it]);
}
if(low[u]==dfn[u]) {
belong[0]++;
while(stak[top]!=u) {
belong[stak[top]]=belong[0];
vis[stak[top]]=0;
top--;
}
belong[u]=belong[0];
vis[u]=0;
top--;
}
}
int ru[N];
map<pair<int,int>,int> hasH;
int main() {
n=read(),m=read();
for(int i=1;i<=m;++i) {
int x=read(),y=read();
if(hasH.count(make_pair(x,y))) continue;
hasH[make_pair(x,y)]=1;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;++i)
if(!dfn[i])
tarjan(i,0);
for(int i=1;i<=n;++i) {
for(iter it=G[i].begin();it!=G[i].end();++it) {
if(belong[i]!=belong[*it]) {
ru[belong[i]]++,ru[belong[*it]]++;
}
}
}
int ans=0;
for(int i=1;i<=n;++i) if(ru[i]==2) ans++;
printf("%d
",(ans+1)/2);
return 0;
}