50分求调subtask3&4 WA两个其余TLE
查看原帖
50分求调subtask3&4 WA两个其余TLE
305735
Jean_Gunnhildr楼主2024/8/12 13:06
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
const int M=2000005;
int n,m;
int pre[M*2],k;
struct node{
	int from,to,next,difference;
	bool can;
}edge[M*2];

void add(int fr,int d,int dif){
	k++;
	edge[k].from=fr;
	edge[k].to=d;
	edge[k].difference=dif;
	edge[k].can=true;
	edge[k].next=pre[fr];
	pre[fr]=k;
}
int dfn[N],low[N],num;

void tarjan(int id,int differ){
	dfn[id]=low[id]=++num;
	for(int i=pre[id];i!=0;i=edge[i].next){
		if(edge[i].difference==differ) continue;
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan(y,edge[i].difference);
			low[id]=min(low[id],low[y]);
			if(low[y]>dfn[id]){
				edge[i].can=false;//同一条边的id号肯定差为+-1,比较+-1两条边的difference来把同一条边都标记为割边
				if(edge[i-1].difference==edge[i].difference) edge[i-1].can=false;
				else if(edge[i+1].difference==edge[i].difference) edge[i+1].can=false;
			}
		}
		else low[id]=min(low[id],dfn[y]);
	}
}
bool vis[N]={false};//标记是否访问过
int ans=0;//计数
vector<int> a[N];//存储每一个边双连通分量

void dfs(int id){
	vis[id]=true;
	a[ans].push_back(id);
	for(int i=pre[id];i!=0;i=edge[i].next){
		if(edge[i].can==false||vis[edge[i].to]) continue;
		else dfs(edge[i].to);
	}
	return ;
}

int main(){
	scanf("%d%d",&n,&m);
	edge[0].difference=-1;
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v,i);//用edge[].difference来区分是不是同一条边
		add(v,u,i);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){//防止图不是连通的
			tarjan(i,-1);
		}
	}
	
//	for(int i=1;i<=k;i++){
//		if(edge[i].can==false) cout<<edge[i].from<<' '<<edge[i].to<<endl;
//	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		ans++;
		dfs(i);//找边双连通分量
	}
	printf("%d\n",ans);
	for(int i=1;i<=ans;i++){
		printf("%d ",a[i].size());
		for(auto j:a[i]) printf("%d ",j);
		printf("\n");
	}
	return 0;
}
2024/8/12 13:06
加载中...