首页 > 代码库 > UVa 10763 - Foreign Exchange
UVa 10763 - Foreign Exchange
题目:给你一个图的边集,问是不是多有的边都有回边。
分析:图论,排序。直接排序查找判定即可。
按照边的最小端点,和最大端点排序,则成对的边(或者相同的边)一定相邻。
说明:(⊙_⊙)。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef struct snode { int a,b,l,r; }student; student S[500001]; int U[500001]; int cmp(student p, student q) { if (p.l == q.l) return p.r < q.r; return p.l < q.l; } int main() { int n,x,y; while (~scanf("%d",&n) && n) { for (int i = 0 ; i < n ; ++ i) { scanf("%d%d",&x,&y); S[i].a = x; S[i].b = y; S[i].l = min(x, y); S[i].r = max(x, y); } int flag = 1; if (n%2 == 0) { sort(S, S+n, cmp); memset(U, 0, sizeof(U)); for (int k,j,i = 0 ; i < n ; ++ i) if (!U[i]) { U[i] = 1; j = i+1; k = 0; while (S[j].l == S[i].l && S[j].r == S[i].r) { if (!U[j] && S[i].a == S[j].b && S[i].b == S[j].a) { U[j] = 1; k = 1; break; } j ++; } if (!k) { flag = 0; break; } } }else flag = 0; if (flag) printf("YES\n"); else printf("NO\n"); } return 0; }
UVa 10763 - Foreign Exchange
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。