Tarjan 没过样例求调!
查看原帖
Tarjan 没过样例求调!
1008513
xiaoshumiao楼主2023/12/2 08:59
#include<cstdio>
#include<vector>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int MAXN=20005;
vector<int>edge[MAXN];
int num[MAXN],low[MAXN],index;
bool flag[MAXN];
void Tarjan(int cur,bool root) {
  int ch=0;
  index++;
  num[cur]=low[cur]=index;
  for(int k,len=edge[cur].size();k<len;k++) {
  	int i=edge[cur][k];
  	if(num[i]==0) {
  	  Tarjan(i,false);
  	  low[cur]=min(low[cur],low[i]);
  	  if(!root&&low[i]>=num[cur])
  	  	flag[cur]=true;
  	  if(root)
  	    ch++;
  	}
  	else
  	  low[cur]=min(low[cur],num[i]);
  }
  if(ch>=2&&root)
    flag[cur]=true;
}
int main() {
  int n,m;
  scanf("%d %d",&n,&m);
  for(int i=1,x,y;i<=m;i++) {
  	scanf("%d %d",&x,&y);
  	edge[x].push_back(y);
  	edge[y].push_back(x);
  }
  for(int i=1;i<=n;i++) {
  	if(num[i]==0)
  	  Tarjan(i,true);
  }
  int cnt=0;
  for(int i=1;i<=n;i++) {
  	if(flag[i])
  	  cnt++;
  }
  printf("%d\n",cnt);
  for(int i=1;i<=n;i++) {
  	if(flag[i])
  	  printf("%d\n",i);
  }
  return 0;
}
2023/12/2 08:59
加载中...