社区讨论

样例过了全wa求调

B3609[图论与代数结构 701] 强连通分量参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m07nk0la
此快照首次捕获于
2024/08/24 12:40
2 年前
此快照最后确认于
2025/11/04 22:34
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll scc,inst[1000005],ti,n,m,head[1000005],cnt,dfn[1000005],low[1000005];
struct Edge{
	ll next,to;
}e[1000005];
vector<ll> ans[1000005];
void add(ll next,ll to){
	e[++cnt].to=to;
	e[cnt].next=head[next];
	head[next]=cnt;
}
stack<ll> s;
void tarjan(ll x){
	dfn[x]=low[x]=++ti;
	s.push(x);
	inst[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(inst[x]){
			low[x]=min(low[x],low[y]);
		}
	}
		if(dfn[x]==low[x]){
			int y;
			scc++;
			do{
				y=s.top();
				ans[scc].push_back(y);
				s.pop();
			}while(x!=y); 
			
		} 
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	cout<<scc<<endl;
	for(int i=1;i<=scc;i++){
		sort(ans[i].begin(),ans[i].end());
	}
	sort(ans+1,ans+scc+1);
	for(int i=1;i<=scc;i++){
		for(ll &j : ans[i]){
			cout<<j<<" ";
		}
		cout<<endl;
	}
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...