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