为何开100倍空间才能过
查看原帖
为何开100倍空间才能过
161876
201810tflsdjl楼主2021/8/28 11:08
#include <cstdio>
#include <iostream>
#include <vector>
using std::vector;

const int Maxn=105;
struct Edge{
	int u, v;
} edge[Maxn];
int n, a, dfn[Maxn], low[Maxn], rd[Maxn], cd[Maxn], cnts, cntedge, cnt[Maxn], mst[Maxn];
int stack[Maxn], top, cntcd, cntrd, tm;
bool vis[Maxn], mv[Maxn][Maxn];
vector<int> mapp[Maxn];
int max(int xx, int yy) { return xx>yy?xx:yy; }
int min(int xx, int yy) { return xx<yy?xx:yy; }
void tarjan(int);

int main(){
	freopen("data.in", "r", stdin);

	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		while(true){
			scanf("%d", &a);
			if(a==0) break;
			edge[cntedge].u = i;
			edge[cntedge].v = a;
			cntedge++;
			mapp[i].push_back(a);
			cnt[i]++;
		}
	}
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			tarjan(i);
		}
	}
	for(int i=1; i<=n; i++){
//		mapp[i].clear();
	}
	for(int i=0; i<cntedge; i++){
		if(mst[edge[i].u]!=mst[edge[i].v] && (!mv[mst[edge[i].u]][mst[edge[i].v]])){
//			mapp[mst[edge[i].u]].push_back(mst[edge[i].v]);
//			cnt[mst[edge[i].u]]++;
			mv[mst[edge[i].u]][mst[edge[i].v]] = true;
			rd[mst[edge[i].v]]++;
			cd[mst[edge[i].u]]++;
		}
	}
	for(int i=0; i<cnts; i++){
		if(rd[i]==0) cntrd++;
		if(cd[i]==0) cntcd++;
	}
	printf("%d\n", cntrd);
	if(cnts==1){
		printf("0\n");
	}
	else{
		printf("%d\n", max(cntrd, cntcd));
	}

	return 0;
}

void tarjan(int point){
	vis[point] = true;
	low[point] = (++tm);
	dfn[point] = low[point];
	stack[top++] = point;
	for(int i=0; i<cnt[point]; i++){
		if(!vis[mapp[point][i]]){
			tarjan(mapp[point][i]);
			low[point] = min(low[point], low[mapp[point][i]]);
		}
		else{
			for(int i=0; i<top; i++){
				if(stack[i]==mapp[point][i]){
					low[point] = min(low[point], low[mapp[point][i]]);
					break;
				}
			}
		}
	}
	if(dfn[point]==low[point]){
		while(stack[top]!=point && top!=0){
			mst[stack[--top]] = cnts;
//			scc[cnts][scnt[cnts]++] = stack[--top];
		}
		cnts++;
	}
}

RT,这份代码无法通过#10和#11

但是将第六行 Maxn 的值改为 1005 后可以AC #10

改为 10005 后可以AC #11

求助,这是为什么呢,我看不出来什么越界问题

2021/8/28 11:08
加载中...