Tarjan 0分求助,样例不输出。
查看原帖
Tarjan 0分求助,样例不输出。
1008513
xiaoshumiao楼主2023/12/14 08:49
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN=155,MAXM=5005;
vector<int>edge[MAXN];
int num[MAXN],low[MAXN],index,fa,cnt;
struct Edge {
  int a,b;
}ans[MAXM];
bool cmp(Edge a,Edge b) {
  if(a.a==b.a)
    return a.b<b.b;
  return a.a<b.a;
}
void Tarjan(int cur) {
  int ch=0;
  index++;
  num[cur]=low[cur]=index;
  for(int j=0,len=edge[cur].size();j<len;j++) {
  	int i=edge[cur][j];
  	if(num[i]==0) {
  	  ch++;
  	  Tarjan(i);
  	  if(low[i]<low[cur])
  	    low[cur]=low[i];
  	  if(cur!=fa&&low[i]>num[cur]) {
  	  	cnt++;
  	  	if(cur<i) {
  	  	  ans[cnt].a=cur;
  	  	  ans[cnt].b=i;
  	  	}
  	  	else {
  	  	  ans[cnt].b=cur;
  	  	  ans[cnt].a=i;
  	  	}
  	  }
  	}
  	else
  	  if(num[i]<low[cur])
  	    low[cur]=num[i];
  }
}
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) {
  	  fa=i;
	  Tarjan(i);
  	}
  }
  for(int i=1;i<=cnt;i++)
    printf("%d %d\n",ans[i].a,ans[i].b);
  return 0;
}
2023/12/14 08:49
加载中...