RE on test 47
查看原帖
RE on test 47
131591
蒟蒻君HJT泽渡透香楼主2023/1/1 17:05

求助

#include <bits/stdc++.h>
inline int read(){
	int x = 0;
	char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
	return x;
}
const int N = 5e5 + 5;
int n, m, low[N], dfn[N], dsum = 0;
int st[N], tp = 0, cnt = 0;
std::vector <int> ds[8 * N], ver[N];
void tarjan(int x, int fa){
  int s = 0;
  dfn[x] = low[x] = ++dsum;
  st[++tp] = x;
  for(int i = 0; i < ver[x].size(); ++i){
    int y = ver[x][i];
    if(!dfn[y]){
  	  ++s;
	  tarjan(y, x);
	  low[x] = std::min(low[x], low[y]);
	  if(low[y] >= dfn[x]){
	    ++cnt;
	    while(st[tp] != y) 
	      ds[cnt].push_back(st[tp--]);
	    ds[cnt].push_back(st[tp--]);
	    ds[cnt].push_back(x);
	  }
    }
    else low[x] = std::min(low[x], dfn[y]);
  }
  if(!s && !fa) ++cnt, ds[cnt].push_back(x), --tp;
  return ;
}
int main(){
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i){
	int x, y;
	x = read(), y = read();
	ver[x].push_back(y);
	ver[y].push_back(x);
  }
  for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i, 0), tp = 0;
  printf("%d\n", cnt);
  for(int i = 1; i <= cnt; ++i){
    printf("%d ", (int)(ds[i].size()));
    for(int j = 0; j < ds[i].size(); ++j) printf("%d ", ds[i][j]);
    printf("\n");
  } 
  return 0;
}

RE 在特判独立点那里,如果去掉 --tp 的话就是 WA,为什么呢?

2023/1/1 17:05
加载中...