数据好水。。。
查看原帖
数据好水。。。
673643
GameFreak楼主2022/7/16 22:46

同样一份代码,洛谷上面A了,在学校OJ上面爆了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int Min(int x,int y){
	return x<y?x:y;
}
int Max(int x,int y){
	return x>y?x:y;
}
int to[100001],head[100001],nex[100001],cnt=-1;
void add(int u,int v){
	to[++cnt]=v;
	nex[cnt]=head[u];
	head[u]=cnt;
}
int n=read(),m=read();
int tot,root;
int dfn[100001],low[100001];
int k[100001],dcc;
bool bridge[100001];
void Tarjan(int u,int edge){
	dfn[u]=low[u]=++tot;
	for(int i=head[u];i!=-1;i=nex[i]){
		int v=to[i];
		if(!dfn[v]){
			Tarjan(v,i);
			low[u]=Min(low[u],low[v]);
			if(dfn[u]<low[v]) bridge[i]=bridge[i^1]=1;
		}
		else if(i!=(edge^1)) low[u]=Min(low[u],dfn[v]);
	}
}
void dfs(int u){
	k[u]=dcc;
	for(int i=head[u];i!=-1;i=nex[i]){
		int v=to[i];
		if(k[v]||bridge[i]) continue;
		dfs(v);
	}
}
int intr[100001];
int main(){
	for(int i=1;i<=n;i++) head[i]=-1;
	for(int i=1;i<=m;i++){
		int a=read(),b=read();
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,-1);
	for(int i=1;i<=n;i++)
		if(!k[i]){
			dcc++;
			dfs(i);
		}
	for(int u=1;u<=n;u++){
		for(int i=head[u];i!=-1;i=nex[i]){
			if(k[u]!=k[to[i]]){
				intr[k[to[i]]]++;
				intr[k[u]]++;
			}
		}
	}
	int leaf=0;
	for(int i=1;i<=dcc;i++) if(intr[i]==2) leaf++;
	printf("%d",(1+leaf)/2);
	return 0;
}

哪位大神帮我看看?(蒟蒻快疯了)

2022/7/16 22:46
加载中...