1 条题解
-
0

#include<bits/stdc++.h> using namespace std; const int N=500010; int n,m; int dfn[N],low[N],stk[N],top,cnt,root,cut[N]; vector<int> e[N],dcc[N]; void tarjan(int x){ dfn[x]=low[x]=++dfn[0]; stk[++top]=x; if(x==root&&!e[x].size()){ //孤立点 dcc[++cnt].push_back(x); return; } int son=0; for(int y:e[x]){ if(!dfn[y]){ //若y未访问 tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ //x是割顶 son++; if(x!=root||son>1)cut[x]=1; //记录割点 // 每次回到割顶时记录vDCC ++cnt; for(int z=-1;z!=y;){ //让x留在栈中 z=stk[top--]; dcc[cnt].push_back(z); } dcc[cnt].push_back(x); //记录vDCC } } else //若y已访问 low[x]=min(low[x],dfn[y]); } } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m; for(int a,b;m--;){ cin>>a>>b; if(a==b) continue; //忽略自环 e[a].push_back(b), e[b].push_back(a); } for(root=1;root<=n;root++)if(!dfn[root])tarjan(root); cout<<cnt<<"\n"; for(int i=1;i<=cnt;i++){ cout<<dcc[i].size()<<" "; for(int j:dcc[i])cout<<j<<" "; cout<<"\n"; } }
#include<bits/stdc++.h> using namespace std; const int N=10010; int n,m,a,b; vector<int> e[N],ne[N],dcc[N]; int dfn[N],low[N],tot,stk[N],top,cut[N],root,cnt; int id[N]; void tarjan(int x){ dfn[x]=low[x]=++tot; stk[++top]=x; if(x==root&&!e[x].size()){ //孤立点 dcc[++cnt].push_back(x); return; } int son=0; for(int y:e[x]){ if(!dfn[y]){ //若y未访问 tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ son++; if(x!=root||son>1)cut[x]=1; //割点 ++cnt; while(1){ int z=stk[top--]; dcc[cnt].push_back(z); if(z==y) break; //让x留在栈中 } dcc[cnt].push_back(x); //vDCC } } else //若y已访问 low[x]=min(low[x],dfn[y]); } } int main(){ cin>>n>>m; while(m--){ cin>>a>>b; e[a].push_back(b), e[b].push_back(a); } for(root=1;root<=n;root++)if(!dfn[root])tarjan(root); //给每个割点一个新编号(cnt+1开始) int num=cnt; for(int i=1;i<=n;i++)if(cut[i])id[i]=++num; //建树,从每个缩点向对应割点连边 for(int i=1;i<=cnt;i++){ for(int j=0;j<dcc[i].size();j++){ int x=dcc[i][j]; if(cut[x]){ ne[i].push_back(id[x]), ne[id[x]].push_back(i); } } } }
- 1
信息
- ID
- 12508
- 时间
- 2000ms
- 内存
- 600MiB
- 难度
- 10
- 标签
- 递交数
- 5
- 已通过
- 3
- 上传者