由题意可知,一定存在一条连接i与i+1的边,因为只存在一个简单环,所以除了i到i+1的边之外,只能有一条边覆盖i到i+1这个位置,这样就转成了线段覆盖问题1234567891011121314151617181920212223242526272829303132333435363738394041424344#include#include#includeusingnamespacestd;intn,m,tot,cur;structnode{intx,y;}e[200003];boolcmp(constnode&s1;,constnode&s2;){returns1.y<=m;i++){intx,y;scanf("%d%d",&x;,&y;);if(x>y)swap(x,y);if(x+1!=y){e[++t].x=x;e[t].y=y;}}sort(e+1,e+t+1,cmp);for(inti=1;i<=t;i++)if(e[i].x>=cur){cur=e[i].y;tot++;}printf("%d\n",tot+n-1);return0;}
...
继续阅读
(18)