C++(g++ 7.5.0) 解法, 执行用时: 32ms, 内存消耗: 32684K, 提交时间: 2022-10-23 22:13:31

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define int long long
#define M 1000005
int n,m;
int x[M],y[M];
vector<int>v[M];
int dfn[M],low[M],tot;
int sta[M],vis[M],top;
int scc[M],siz[M],cnt;
int fa[M];
int f[5005][5005];
void tarjan(int x){
    dfn[x]=low[x]=++tot;
    sta[++top]=x;vis[x]=1;
    for(int y:v[x]){
        if(!dfn[y]){
            fa[y]=x;    //标记
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(y!=fa[x]){
            low[x]=min(low[x],dfn[y]);
        }
    }
    if(dfn[x]==low[x]){
        ++cnt;
        int y;
        do{
            y=sta[top--];
            vis[y]=0;
            scc[y]=cnt;
            ++siz[cnt];
        }while(y!=x);
    }
}
int pre[M],sum=0;
signed main(){
    memset(fa,-1,sizeof(fa));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x[i]>>y[i];
        if(f[x[i]][y[i]]) continue;
        f[x[i]][y[i]]=f[y[i]][x[i]]=1;
        v[x[i]].push_back(y[i]);		//无向图
        v[y[i]].push_back(x[i]);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++){
        for(int c:v[i]){
            pre[scc[i]]+=(scc[c]!=scc[i]);
        }
    }
    for(int i=1;i<=cnt;i++){
        sum+=(pre[i]==1);
    }
    cout<<(sum+1)/2<<endl;
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 2ms, 内存消耗: 432K, 提交时间: 2023-08-06 19:13:30

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5010;
const int M=2e4+5;
int n,m;
int h[N],num,ne[M],to[M];
int dfn[N],low[N],timestamp;
int stk[N],top;
bool is_[M];
int dcc_cnt,id[N];
int d[N];
void add(int a,int b){
	ne[num]=h[a],to[num]=b,h[a]=num++;
}
void tarjan(int u,int from){
	dfn[u]=low[u]=++timestamp;
	stk[++top]=u;
	for(int i=h[u];~i;i=ne[i]){
		int j=to[i];
		if(!dfn[j]){
			tarjan(j,i);
			low[u]=min(low[u],low[j]);
			if(low[j]>dfn[u])
				is_[i]=is_[i^1]=1;
		}
		if(i!=(from^1))
			low[u]=min(low[u],dfn[j]);
	}
	if(dfn[u]==low[u]){
		dcc_cnt++;
		int y;
		do{
			y=stk[top--];
			id[y]=dcc_cnt;	
		}while(y!=u);
	}
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof(h));
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	tarjan(1,-1);
    for(int i=0;i<=num;i++)
        if(is_[i])
            d[id[to[i]]]++;
	int ans=0;
	for(int i=1;i<=dcc_cnt;i++)
		if(d[i]==1)
			ans++;
	cout<<(ans+1)/2<<endl;
	return 0;
}