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;
}
}
求问各位大佬为什么不对