社区讨论
样例过了,零分求调
B3609[图论与代数结构 701] 强连通分量参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m5t4yt0z
- 此快照首次捕获于
- 2025/01/12 12:49 去年
- 此快照最后确认于
- 2025/01/12 17:27 去年
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int z[10005][10005];
int dfn[10005];//dfn[i]代表第iu个点是第几个
int low[1005];
int belong[10005][10005],cnt=0,op[10005];
int t;
stack<int> s;
bool instack[10005];
bool used[10005];
void add_edge(int p1,int p2){
z[p1][++z[p1][0]]=p2;
}
void dfs(int now){
t++;
dfn[now]=low[now]=t;
s.push(now);
instack[now]=true;
for(int i=1;i<=z[now][0];i++){
if(dfn[z[now][i]]==0){
dfs(z[now][i]);
low[now]=min(low[now],low[z[now][i]]);
}else{
if(instack[z[now][i]]){
low[now]=min(low[now],dfn[z[now][i]]);
}
}
}
if(dfn[now]==low[now]){
cnt++;
while(s.top()!=now){
belong[cnt][++belong[cnt][0]]=s.top();
op[s.top()]=cnt;
instack[s.top()]=false;
s.pop();
}
belong[cnt][++belong[cnt][0]]=s.top();
op[s.top()]=cnt;
instack[s.top()]=false;
s.pop();
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int p1,p2;
cin>>p1>>p2;
add_edge(p1,p2);
}
for(int i=1;i<=n;i++){
if(dfn[i]==0) dfs(i);
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
if(used[op[i]]==0){
used[op[i]]=1;
sort(belong[op[i]]+1,belong[op[i]]+belong[op[i]][0]+1);
for(int j=1;j<=belong[op[i]][0];j++){
cout<<belong[op[i]][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...