求把题目划分为两个部分的可行方案种类数
因为要满足div1的都要比div2的大
同时给出一对要在两个div
并且这个关系不传递
所以对于给出的每一对
大的必须要在div1
小的必须在div2
同时更新div1中的最小值和div2的最大值
最后若div1的最小值没有超过div2的最大值
则一定无法划分
否则min-max的题目都有两种划分方法
其余的有一种划分方法
所以方案数为min-max
若没给任何对关系
则方案数为n-1
#include<stdio.h>
#include<string.h>
//int a[100200];
int main() {
int n,m;
while(scanf("%d %d",&n,&m)!=EOF) {
// memset(a,0,sizeof(a));
int min=n,max=0;
while(m--) {
int x,y;
scanf("%d %d",&x,&y);
// a[x]=a[y]=1;
int t=x>y?x:y;
min=min>t?t:min;
t=x<y?x:y;
max=max<t?t:max;
}
if(min<=max) {
printf("0
");
continue;
}
printf("%d
",min-max==n?n-1:min-max);
}
return 0;
}