点双模板TLE求调(悬关)
查看原帖
点双模板TLE求调(悬关)
300166
Zikl楼主2023/11/8 21:12
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define int long long
using namespace std;
const int N=5e5+5,M=2e6+5;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int n,m,root; 
int head[M],ver[M],Next[M],tot;
void add(int x,int y){
	ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
int dfn[N],low[N],cnt,cntt,stack_[2*M],top;
vector<int>dcc[N];
void tarjan(int x){
	if(x==root&&head[x]==0){
		dcc[++cntt].push_back(x);
		return;
	}
	dfn[x]=low[x]=++cnt;
	stack_[++top]=x;
	for(int i=head[x];i;i=Next[i]){
		int y=ver[i];
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				cntt++;
				while(1){
					dcc[cntt].push_back(stack_[top]);
					top--;
					if(stack_[top+1]==y) break;
				}
				dcc[cntt].push_back(x);
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		if(u==v) continue;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++)
	if(!dfn[i])
	root=i,tarjan(i);
	printf("%lld\n",cntt);
	for(int i=1;i<=cntt;i++){
		printf("%lld ",dcc[i].size());
		for(int j=0;j<dcc[i].size();j++)
		printf("%lld ",dcc[i][j]);
		putchar('\n');
	}
	return 0; 
} 

怎么回事呢

2023/11/8 21:12
加载中...