poj1944

一道我不会做的贪心题。

（思维才是OI的重点）

但是if您也不会，那就来听我瞎扯吧。

首先，这个图是一个圈，只能连接邻点，使所有求的点联通。

我们先不考虑环，那么就可以想出一个假的做法：用一个a数组记录入度和出度，出度为正，入度为负，用一个sum=0从0遍历每个点记录当前出入度，每次加ai，若sum大于0给答案加上1就行了。

然后，我们来考虑环。我们发现。不管怎么连这个图，肯定都会有一个断边的，连接的路径绝不会是一个完整的环。因为如果连成了完整地环，肯定有一条边断掉这个图还是联通的，即这条边是无用的。那么，我们欺负n小就可以分别从第i个点出发像上述查找一条链的做法一样地计算，然后取最大值就行了。

#include
#include
#include
#include
using namespace std;
inline int read()
{
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return w?-x:x; } const int maxn=1010,maxm=10010; int n,m,a[maxn],l[maxm],r[maxm]; int main() { n=read(),m=read(); for(int i=0;iy)swap(x,y);
a[x]++;
a[y]--;
}
int now=0,pre=0;
for(int i=0;i<n;i++){
now+=a[i];
if(now)pre++;
}
if(pre<ans)ans=pre;
}
printf("%d\n",ans);
return 0;
}