社区讨论

50分求助

P8436【模板】边双连通分量参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo1u6iyl
此快照首次捕获于
2023/10/23 03:03
2 年前
此快照最后确认于
2023/11/03 03:35
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;

const int Kmaxb=2e6+5,Kmaxd=5e5+5;

struct E{
    int to,nex;
}e[Kmaxb*2];

int n,m,tot=1,head[Kmaxb];

void add(int x,int y){
    e[++tot].to=y,e[tot].nex=head[x],head[x]=tot;
}

int dn,dfn[Kmaxd],low[Kmaxd];
bool brg[Kmaxd];

void tarjan(int x, int in_edge) {
	dfn[x]=low[x]=++dn;
	for (int i=head[x];i;i=e[i].nex) {
		int y=e[i].to;
		if (!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if (low[y]>dfn[x]) brg[i]=brg[i^1]=true;
		}
		else if (i!=(in_edge^1)){
		    low[x]=min(low[x],dfn[y]);
		}
	}
}

int c[Kmaxd],sl=0;
vector <int> ans[Kmaxd];
void dfs(int x) {
	c[x] = sl;
	if(x) ans[sl].push_back(x); 
	for (int i=head[x];i;i=e[i].nex) {
		int y=e[i].to;
		if (c[y] || brg[i]) continue;
		dfs(y);
	}
}
int main(){
//    freopen("1.in","r",stdin);
//    freopen("1.out","w",stdout);
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
    for(int i=1;i<=n;i++){
        if(!c[i]){
            sl++;
            dfs(i);
        }
    }
    cout<<sl<<endl;
    for(int i=1;i<=sl;i++){
        cout<<ans[i].size();
        for(int j=0;j<ans[i].size();j++){
            cout<<" "<<ans[i][j];
        }
        cout<<endl;
    }
}

回复

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

正在加载回复...