1 条题解
-
0

// eDCC缩点 Tarjan算法 O(n+m) #include<bits/stdc++.h> using namespace std; const int N=500010,M=4000010; int to[M],ne[M],h[N],idx=1; //2,3异或配对 void add(int a,int b){ to[++idx]=b,ne[idx]=h[a],h[a]=idx; } int n,m; int dfn[N],low[N],stk[N],top,cnt; // bool bri[M]; //标记桥 vector<int> dcc[N]; //记录eDCC内的点 void tarjan(int x,int e){ dfn[x]=low[x]=++dfn[0]; stk[++top]=x; for(int i=h[x];i;i=ne[i]){ int y=to[i]; if(!dfn[y]){ //若y未访问 tarjan(y,i); low[x]=min(low[x],low[y]); // if(low[y]>dfn[x]) bri[i]=bri[i^1]=1; } else if(i!=(e^1)) //若y已访问且不是反边 low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ //若x是edcc的根 ++cnt; while(stk[top+1]!=x) dcc[cnt].push_back(stk[top--]); } } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int a,b;m--;)cin>>a>>b,add(a,b),add(b,a); for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i,0); //eDCC缩点 cout<<cnt<<"\n"; for(int i=1;i<=cnt;i++){ //枚举缩点 cout<<dcc[i].size()<<" "; for(int j:dcc[i]) cout<<j<<" "; cout<<"\n"; } }
- 1
信息
- ID
- 12507
- 时间
- 2000ms
- 内存
- 600MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 3
- 上传者