社区讨论
RE求条必关
B3609[图论与代数结构 701] 强连通分量参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mm4htsmb
- 此快照首次捕获于
- 2026/02/27 14:10 上周
- 此快照最后确认于
- 2026/02/28 23:00 上周
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10;
int n,m,h[N],e[N],ne[M],id;
int dfn[N],low[N],idx=0,ins[N],scc[N],ans[N][N],siz[N],cnt,f[N];
stack<int>st;
void add(int a,int b){
id++;
e[id]=b;
ne[id]=h[a];
h[a]=id;
}
//入x的时候,盖戳,入栈
//枚举x的相邻点y
//1.未访问(树枝边)(1)深搜y(2)更新low[x]
//2.已访问在栈中(返祖边)(1)更新low[x]
//3.已访问不在栈中(横叉边)
//离开x的时候,出栈,更新scc
//处理非连通图
void tarjan(int u){
dfn[u]=++idx;
low[u]=idx;
ins[u]=true;
st.push(u);
for(int i=h[u];i;i=ne[i]){
int v=e[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
++cnt;
while(1){
int v=st.top();
st.pop();
ins[v]=false;
scc[v]=cnt;
ans[cnt][++siz[cnt]]=v;
if(v==u)break;
}
}
}
int main(){
cin>>n>>m;
memset(h,0,sizeof(h));
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
cout<<cnt<<endl;
for(int i=1;i<=cnt;i++){
sort(ans[i]+1,ans[i]+siz[i]+1);
}
for(int i=1;i<=n;i++){
if(f[i])continue;
for(int j=1;j<=siz[scc[i]];j++){
f[ans[scc[i]][j]]=1;
cout<<ans[scc[i]][j]<<" ";
}
cout<<endl;
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...