社区讨论

样例3,4没过,求助qwq

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@mhj8ylwy
此快照首次捕获于
2025/11/03 22:40
4 个月前
此快照最后确认于
2025/11/03 22:40
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;

int n,m,tot,num,cnt,root;
int ver[(int)4e6+10],nex[(int)4e6+10],head[(int)5e5+10],dfn[(int)5e5+10],low[(int)5e5+10];
bool cut[(int)4e6+10],yzy[(int)5e5+10];
vector < vector<int> > c; 
vector <int> pjr(1);
stack <int> dcc;

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

void tarjan(int x) {
	dfn[x]=low[n]=++cnt;
	dcc.push(x);
	int y,z,flag=0;
	if(x==root&&head[x]==0){
		yzy[x]=true;
		pjr[0]=x;
		c.push_back(pjr);
		num++;
		return ;
	}
	for(int i=head[x];i;i=nex[i]){
		y=ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				flag++;
				if(x!=root||flag>1) cut[x]=true;
				pjr[0]=x;
				c.push_back(pjr);
				yzy[x]=true;
				num++;
				do{
					z=dcc.top();
					c[num-1].push_back(z);
					yzy[z]=true;
					dcc.pop();
				}while(z!=y);
				//c[num-1].push_back(dcc.top());
				//yzy[dcc.top()]=true;
				//dcc.pop();
				
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}

int main(){
	freopen("in.txt","r",stdin);
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		add(x,y),add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) root=i,tarjan(i);
	}
	cout<<num+1<<endl;
	for(int i=0;i<c.size();i++){
		cout<<c[i].size()<<" ";
		for(int j=0;j<c[i].size();j++){
			cout<<c[i][j]<<" ";
		}
		cout<<endl;
	}
	for(int i=1;i<=n;i++) if(!yzy[i]) pjr.push_back(i);
	if(pjr.size()>1){
		cout<<pjr.size()-1<<" ";
		for(int i=1;i<pjr.size();i++) cout<<pjr[i]<<" ";
	}
	return 0;
}

回复

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

正在加载回复...