一只大龙猫 @ 2021-08-29 09:09:06
样例已过,但是全都WA了。Tarjan 算法,链式前向星存图。
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int n,m,u,v,tot,head[1000001],dfn[1000001],low[1000001],index_,cnt,scc[1000001];
bool inst[1000001],vis[1000001];
struct edge{
int u,v,next;
}g[1000001];
stack<int> st;
void addedge(int u,int v){
g[++tot].u=u;
g[tot].v=v;
g[tot].next=head[u];
head[u]=tot;
return;
}
void tarjan(int u) {
dfn[u]=low[u]=++index_;
st.push(u);
inst[u]=1;
for(int i=head[u];i!=-1;i=g[i].next){
int v=g[i].v;
if(dfn[v]==-1) {
tarjan(v);
low[u]=min(low[u],low[v]);
}else{
if(inst[v]){
low[u]=min(low[u],dfn[v]);
}
}
}
if(dfn[u]==low[u]){
cnt++;
int v;
do{
v=st.top();
st.pop();
scc[v]=cnt;
inst[v]=0;
}while(u!=v);
}
return;
}
int main(){
cin>>n>>m;
memset(head,-1,sizeof(head));
memset(dfn,-1,sizeof(dfn));
for(int i=1;i<=m;i++){
cin>>u>>v;
addedge(u,v);
}
tarjan(1);
cout<<cnt<<endl;
for(int i=1;i<=n;i++){
if(vis[scc[i]])continue;
vis[scc[i]]=1;
for(int j=1;j<=n;j++){
if(scc[j]==scc[i])cout<<j<<" ";
}
cout<<endl;
}
return 0;
}
by Exber @ 2021-08-29 09:16:46
@一只大龙猫 不保证图联通
by 一只大龙猫 @ 2021-08-29 09:19:04
@lovely_ckj A了,谢谢