有可能是你的Tarjan求割点的时候,割点求到了root上,当你用a、b中的一个点作为tarjan的root时,并且你的tarjan中存在求割顶(root为割点)的部分时,你会判断你的root,也就是a或者b,是不是割点。在遍历所有符合答案的割点寻找答案的时候就会因为你判断了a或b之中一个点为答案之一,并且这个a或b的编号是最小的而WA。
WA tarjan
vector<int> low(N,0),dfn(N, 0);
vector<bool> isAns(N, false);
int cnt = 0,root;
int start,target;
void tarjan(int cur,int fa) {
low[cur] = dfn[cur] = ++cnt;
int child = 0;
for (auto nxt: adj[cur]) {
if (dfn[nxt] == 0) {
child++;
tarjan(nxt, cur);
low[cur] = min(low[cur], low[nxt]);
if (low[nxt] >= dfn[cur] && cur != root && dfn[target]>=dfn[nxt])
isAns[cur] = true;
} else if (dfn[nxt] < dfn[cur] && nxt != fa) {
low[cur] = min(low[cur], dfn[nxt]);
}
}
if (cur == root && child >= 2)//应该删除这段
isAns[root] = true;
}
AC tarjan
vector<int> low(N,0),dfn(N, 0);
vector<bool> isAns(N, false);
int cnt = 0,root;
int start,target;
void tarjan(int cur,int fa) {
low[cur] = dfn[cur] = ++cnt;
int child = 0;
for (auto nxt: adj[cur]) {
if (dfn[nxt] == 0) {
child++;
tarjan(nxt, cur);
low[cur] = min(low[cur], low[nxt]);
if (low[nxt] >= dfn[cur] && cur != root && dfn[target]>=dfn[nxt])
isAns[cur] = true;
} else if (dfn[nxt] < dfn[cur] && nxt != fa) {
low[cur] = min(low[cur], dfn[nxt]);
}
}
}
希望能帮到你。