tarjan全WA求助

B3609 [图论与代数结构 701] 强连通分量

RisefromtheAshes @ 2023-09-13 21:15:24

rt,悬赏一关注

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#pragma G++ optimize(3)
using namespace std;
int t=0,dfn[100010],low[100010],n,m,cnt=0,lt[100010];
vector<int>g[100010],ans[100010];
bool vis[100010],bj[100010];
stack<int>z;
void dfs(int x)
{
    dfn[x]=++t;
    low[x]=t;
    z.push(x);
    vis[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        if(!dfn[g[x][i]])
        {
            dfs(g[x][i]);
            low[x]=min(low[x],low[g[x][i]]);
        }
        else if(vis[g[x][i]])
        low[x]=min(low[x],dfn[g[x][i]]);
    }
    if(low[x]==dfn[x])
    {
        cnt++;
        while(1)
        {
            int y=z.top();
            ans[cnt].push_back(y);
            lt[y]=cnt;
            z.pop();
            vis[y]=0;
            if(y==x)break;
        }
        sort(ans[cnt].begin(),ans[cnt].end());
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
    for(int i=1;i<=n;i++)
    {
        if(bj[lt[i]])continue;
        bj[lt[i]]=1;
        for(int j=0;j<ans[lt[i]].size();j++)printf("%d ",ans[lt[i]][j]);
        printf("\n");
    }
    return 0;
}

by CarrotMeow @ 2023-09-13 21:33:30

@divinity_ming 好巨 %%%

随便摆个 LCA 板的 Tarjan:

void dfs(int u) { // Tarjan
    fa[u] = u; // 初始化
    vis[u] = 1;
    for (int i : tr[u]) {
        if (vis[i]) continue;
        dfs(i);
        fa[i] = u;
    }
    for (auto [i, j] : q[u]) // q[u] = {i, v} 说明第 i 次询问 lca(u, v)
        if (vis[j]) res[i] = find(j);
}

好像和这题并不一样吧?这种方式是深进推荐的,短


by CarrotMeow @ 2023-09-13 21:35:30

上面代码 find 是并查集的,fa 也是并查集用的数组


by hdkk @ 2023-09-14 14:19:02

您没输出cnt啊。。。加上就过了


by RisefromtheAshes @ 2023-09-14 17:37:13

@hdkk 过了,我是傻逼,%%%dalao


|