Isharmla @ 2023-10-13 17:10:45
求调试。
// Problem: B3609 [图论与代数结构 701] 强连通分量
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3609
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,a,b) for(int i=a;i<=b;i++)
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
const int N=4e5+5;
int head[N],nxt[N],to[N],tot;
inline void AddEdge(int u,int v){
to[++tot]=v;
nxt[tot]=head[u];
head[u]=tot;
}
int cnt,n,m,stk[N],tp,number_scc,dfn[N],low[N];//栈元素,栈顶,SCC的数量
bool In_stk[N];//是否在栈里面
vector<int> S[N];
void Tarjan(int u){
dfn[u]=low[u]=(++cnt);
stk[++tp]=u;In_stk[u]=1;
for(int i=head[u];i;i=nxt[i]){
if(!dfn[to[i]]){
Tarjan(to[i]);
low[u]=min(low[u],low[to[i]]);
}else if(In_stk[to[i]]==1){
low[u]=min(low[u],dfn[to[i]]);
}
}
if(dfn[u]==low[u]){
number_scc++;
while(stk[tp]!=u){
In_stk[tp]=0;
S[number_scc].push_back(stk[tp]);
tp--;
}
In_stk[tp]=0;
S[number_scc].push_back(u);
tp--;
}
}
bool cmp(vector <int> a, vector <int> b) {
return *a.begin() < *b.begin();
}
signed main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
AddEdge(u,v);
}
F(i,1,n){
if(!dfn[i]) Tarjan(i);
}
for (int i=1;i<=number_scc;i++)
sort(S[i].begin(),S[i].end());
sort(S+1,S+1+number_scc,cmp);
cout<<number_scc<<endl;
F(i,1,number_scc){
//sort(S[i].being(),S[i].end());
F(j,0,S[i].size()-1) cout<<S[i][j]<<" ";
cout<<endl;
}
return 0;
}
by UYHW @ 2023-10-13 17:47:59
@Isharmla In_stk[tp]=0
-> In_stk[stk[tp]]