社区讨论

样例过了,零分求调

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 条回复,欢迎继续交流。

正在加载回复...