一段代码求助
查看原帖
一段代码求助
854735
CondorOfLiberty楼主2023/4/10 18:43

A了的代码:

#include<bits/stdc++.h>
using namespace std;
namespace io{
	int read(){
		int x=0;
		char c=0;
		bool f=1;
		do{
			if(c=='-') f=0;
			c=getchar();
		}while(!isdigit(c));
		do{
			x=(x<<3)+(x<<1)+(c^'0');
			c=getchar();
		}while(isdigit(c));
		return f ? x : (~x+1);
	}
}
using namespace io;
const int N=2e5+3, M=1e6+3, INF=0x7fffffff;
struct edge{
	int to, pre;
} a[M];
int idx, h[N];
void add(int x, int y){
	a[++idx].to=y;
	a[idx].pre=h[x];
	h[x]=idx;
}
int dfn[N], lowlink[N], fa[N], cnt;
bool svd[N], gv[N];
void dfs(int x){
	dfn[x]=++cnt, lowlink[x]=cnt, svd[x]=1;
	for(int i=h[x]; i ;i=a[i].pre)
		if(a[i].to==fa[x])  continue;
	else if(svd[a[i].to])  lowlink[x]=min(lowlink[x],dfn[a[i].to]);
	else { fa[a[i].to]=x, dfs(a[i].to), lowlink[x]=min(lowlink[x],lowlink[a[i].to]);
		if( (lowlink[a[i].to]>=dfn[x]) && fa[x])  gv[x]=1;	}
}
int ans=INF;
int n, x, y;
void check(int now){
	while(now && (now!=x)  ){
		if(lowlink[now]>=dfn[fa[now]]&&fa[now]!=x&&fa[now]<ans)  ans=fa[now];
		now=fa[now];
	}
}

int main(){
	n=read();
	while(1){
		x=read(), y=read();
		if(x==0&&y==0)  break;
		add(x, y), add(y, x);
	}
	x=read(), y=read();
	dfs(x), check(y);
	if(ans==INF)  cout<<"No solution";
	else cout<<ans;
	return 0;
}

没A的代码唯一区别是check那里:

void check(int now){
	while(now && now!=x){
		now=fa[now];
		if(now==x)  break;
		if(gv[now] && now<ans && now<ans)  ans=now;
	}
}

求问各位大佬为什么不对

2023/4/10 18:43
加载中...