求卡常
查看原帖
求卡常
117662
那一条变阻器楼主2020/8/28 11:08

这道题是不能这样做吗?

#include <bits/stdc++.h>
using namespace std;
int n , m , tot , p;
int ans[5010] , vis[5010] , dis[5010][5010] , now[5010] , s1[5010] , s2[5010] , cut[5010][5010] , dfn[5010] , low[5010];
void dfs(int x){
	ans[++tot] = x;
	for(int i = 1; i <= n; i++)
		if(dis[x][i] && !vis[i])
			vis[i] = 1 , dfs(i);
}
void tarjan(int x){
	dfn[x] = low[x] = ++p;
	for(int i = 1; i <= n; i++){
		if(!dis[x][i]) continue;
		if(!dfn[i]){
			tarjan(i);
			low[x] = min(low[x] , low[i]);
			if(low[i] > dfn[x] && !cut[i][x]) cut[i][x] = cut[x][i] = 1;
		}else low[x] = min(low[x] , dfn[i]);
	}
}
int main(){
	scanf("%d%d" , &n , &m);
	for(int i = 1; i <= m; i++){
		int x , y;
	scanf("%d%d" , &x , &y);
		s1[i] = x , s2[i] = y;
		dis[x][y] = dis[y][x] = 1;
	}
	for(int i = 1; i <= n; i++) now[i] = 0x3fffff;
	if(m == n - 1){
		vis[1] = 1;
		dfs(1);
		for(int i = 1; i <= n; i++) cout << ans[i] << " ";
	}else{
		tarjan(1);
		int j = 0;
		while(j <= m){
			j++;
			int x = s1[j] , y = s2[j];
			if(cut[x][y]) continue;
			dis[x][y] = dis[y][x] = 0;
			vis[1] = 1;
			tot = 0;
			dfs(1);
			dis[x][y] = dis[y][x] = 1;
			int f = 0;
			for(int i = 1; i <= n; i++){
				if(!vis[i]) f = 1;
				vis[i] = 0;
			}
			if(f) continue;
			f = 1;
			for(int i = 1; i <= n; i++){
				if(now[i] < ans[i]) break;
				if(now[i] > ans[i]){
					f = 0;
					break;
				}
			}
			if(!f) for(int i = 1; i <= n; i++) now[i] = ans[i];
		}
		for(int i = 1; i <= n; i++) cout << now[i] << " ";
	}
	return 0;
}

感谢

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