Subtask #1 WA的一种可能
查看原帖
Subtask #1 WA的一种可能
1003870
Evangel1on楼主2024/4/17 22:35

有可能是你的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]);
        }
    }
}

希望能帮到你。

2024/4/17 22:35
加载中...