星存图思路求助
查看原帖
星存图思路求助
312605
Megumimwf楼主2023/2/1 20:52

如何实现u->v 和 v->u的双向消边 代码如下(dfs中的if是我思考的消边方式但并不成功)

#include<bits/stdc++.h>
using namespace std;

char u, v;
int n, head[1086], tot, ans[1086], ala, minn=0x7f7f7f, maxx, uu[1086], start, degree[1086], cnt, vv[1086];
bool flag;

struct node{
	int uu, vv;
};
struct edge {
	int to, next, cnt;
};
edge e[1086];
node a[1086];
void dfs(int temp) {
	for(int i=head[temp]; i; i=e[i].next) {
		if(e[i].cnt) {
			e[i].cnt = 0;
			if(i&1) {
				e[i+1].cnt = 0;
			} else {
				e[i-1].cnt = 0;
			}
			dfs(e[i].to);
		}
	}
	cnt++;
	ans[cnt] = temp;
}

//bool cmp(node a, node b){
//	if(a.uu == b.uu){
//		return a.vv > b.vv;
//	}else{
//		return a.uu < b.uu;
//	}
//}

void add(int u, int v) {
	tot++;
	e[tot].next = head[u];
	e[tot].to = v;
	e[tot].cnt++;
	head[u] = tot;
}

int main() {
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>u>>v;
		a[i].uu = int(u);
		a[i].vv = int(v);
		add(a[i].uu, a[i].vv);
		add(a[i].vv, a[i].uu);
		degree[a[i].uu]++;
		degree[a[i].vv]++;
		minn = min(minn, min(a[i].uu, a[i].vv));
		maxx = max(maxx, max(a[i].uu, a[i].vv));
	}
	start = minn;
//	for(int i=minn;i<=maxx;++i){
//		cout<<degree[i]<<" ";
//	}
//	sort(a+1, a+1+n, cmp);
//	for(int i=1;i<=n;++i){
//		add(a[i].uu, a[i].vv);
//		add(a[i].vv, a[i].uu);
//	}
	for(int i=minn; i<=maxx; ++i) {
		if(degree[i]&1) {  
			if(!flag) {
				start = i;
			}
			flag = 1;
			ala++;
		}
	}
	if(ala!=2 && ala != 0) {
		cout<<"No Solution";
		return 0;
	}
	dfs(start);
	for(int i=cnt; i>=1; --i) {
		cout<<char(ans[i]);
	}
	return 0;
}
2023/2/1 20:52
加载中...