社区讨论
求助
B3609[图论与代数结构 701] 强连通分量参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo2egyrc
- 此快照首次捕获于
- 2023/10/23 12:31 2 年前
- 此快照最后确认于
- 2023/11/03 13:17 2 年前
CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
inline int read(){
int sum=0,check=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-'){
check=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9'){
sum=(sum<<1)+(sum<<3)+(ch^48);
ch=getchar();
}
return sum*check;
}
int n,m;
int cnt,Time,len,CNT;
int root[N],flag[N];
int head[N],dfn[N],low[N],Stack[N];
bool instack[N];
vector<int> ans[N];
struct node{
int to,next;
}edge[10*N];
void addedge(int from,int to){
cnt++;
edge[cnt].to=from;
edge[cnt].next=head[from];
head[from]=cnt;
}
void tarjan(int n){
dfn[n]=low[n]=++Time;
Stack[++len]=n;
instack[n]=true;
for(int i=head[n];i;i=edge[i].next){
int temp=edge[i].to;
if(!dfn[temp]){
tarjan(temp);
low[n]=min(low[n],low[temp]);
}
else if(instack[temp]){
low[n]=min(low[n],low[temp]);
}
}
if(dfn[n]==low[n]){
CNT++;
while(len>0){
int temp=Stack[len];
len--;
instack[temp]=false;
ans[CNT].push_back(temp);
root[temp]=CNT;
if(temp==n){
break;
}
}
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int temp1=read(),temp2=read();
addedge(temp1,temp2);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
tarjan(i);
}
}
printf("%lld\n",CNT);
for(int i=1;i<=CNT;i++){
sort(ans[i].begin(),ans[i].end());
}
for(int i=1;i<=n;i++){
if(flag[root[i]]){
continue;
}
flag[root[i]]=true;
for(int j=0;j<ans[root[i]].size();j++){
printf("%lld ",ans[root[i]][j]);
}
printf("\n");
}
return 0;
}
全错样例都过不了
回复
共 3 条回复,欢迎继续交流。
正在加载回复...