有关数组大小的问题
查看原帖
有关数组大小的问题
89338
__frj楼主2022/7/15 19:33

RT,这份代码将 NN 设置为 31063*10^6 时会WA后两个点,设置为61066*10^6时可AC,但本题中边数只有51055*10^5,这是为什么呢

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
#define ull unsigned long long
#define gc getchar
using namespace std;
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<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N = 3000007;
int cnt[N],root,n,m,tot,head[N],nxt[N],to[N],dfn[N],low[N],vis[N];
void add(int x,int y){
	to[++tot] = y , nxt[tot] = head[x] , head[x] = tot;
}
int cur = 0;
void dfs(int x,int in_edge){
	dfn[x] = low[x] = ++cur;
	for(int i=head[x];i;i=nxt[i]){
		int y = to[i];
		//if(i == (in_edge ^ 1)) continue;
		//if(dfn[y]) low[x] = min(low[x],dfn[y]); //
		if(!dfn[y]){
			dfs(y,i);
			low[x] = min(low[x],low[y]);
			if(dfn[x] < low[y]){
				vis[i] = vis[i^1] = 1;
			}

		} 
        else if(i != (in_edge ^ 1)){
            low[x] = min(low[x],dfn[y]);
        }
	}
}
int count_dcc = 0;
vector<int> a[500007];
void sfd(int x){
	cnt[x] = 1;
	a[count_dcc].push_back(x);
	for(int i=head[x];i;i=nxt[i]){
		int y = to[i];
		if(cnt[y] || vis[i]) continue;
		sfd(y); 
	}
} 
int main(){
	int n = read() , m =read();
	tot = 1;
	for(int i=1;i<=m;i++){
		int u = read() , v = read();
		add(u,v),add(v,u); 
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) dfs(i,0);
	}
	
	for(int i=1;i<=n;i++){
		if(!cnt[i]){
			count_dcc++;
			sfd(i);		
		}
	}
	cout << count_dcc<<endl;
	for(int i=1;i<=count_dcc;i++){
		cout<<a[i].size()<<" ";
		for(int j=0;j<a[i].size();j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

2022/7/15 19:33
加载中...