仙人掌(cactus)

题目描述
LYK 在冲刺清华集训（THUSC）！于是它开始研究仙人掌，它想来和你一起分享它最近
研究的结果。
如果在一个无向连通图中任意一条边至多属于一个简单环（简单环的定义为每个点至多
经过一次），且不存在自环，我们称这个图为仙人掌。
LYK 觉得仙人掌还是太简单了，于是它定义了属于自己的仙人掌。
定义一张图为美妙的仙人掌，当且仅当这张图是一个仙人掌且对于任意两个不同的点 i,j，
存在一条从 i 出发到 j 的路径，且经过的点的个数为|j-i|+1 个。
给定一张 n 个点 m 条边且没有自环的图，LYK 想知道美妙的仙人掌最多有多少条边。
数据保证整张图至少存在一个美妙的仙人掌。
输入格式(cactus.in)
第一行两个数 n,m 表示这张图的点数和边数。
接下来 m 行，每行两个数 u,v 表示存在一条连接 u,v 的无向边。
输出格式(cactus.out)
一个数表示答案
输入样例
4 6
1 2
1 3
1 4
2 3
2 4
3 4
输出样例
4

思路：

　　题目保证一定存在i到i+1的边。那我就不去处理了。（保证一定存在 1,——2——3——4......n-1——n。这样的链。）

　　只要处理  在 1,——2——3——4......n-1——n。这条链上，加上尽可能多的边，不会出现某一个边被包含在多个环中。

　　咦！这不就转化成了区间覆盖问题了！

dp贪心两种写法。

dp

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

#define MAXN 100010

int f[MAXN],g[MAXN];

int n,m;

int main()

{

    freopen("cactus.in","r",stdin);

    freopen("cactus.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=,u,v;i<=m;i++)

    {

        scanf("%d%d",&u,&v);

        if(u>v)    swap(u,v);

        if(u+!=v) g[v]=max(g[v],u);

    }

    f[]=-;

    for(int i=;i<=n;i++)

    f[i]=max(f[i-],f[g[i]]+);

    printf("%d",f[n]+n-);

    return ;

}

贪心

#include<cstdio>

#include<iostream>

#include<algorithm>

#define N 100010

using namespace std;

int n,m;

struct node

{

    int x,y;

};node e[N*];

bool cmp(const node&s1,const node&s2)

{

    return s1.y<s2.y;

}

int main()

{

    //freopen("cactus.in","r",stdin);

    //freopen("cactus.out","w",stdout);

    scanf("%d%d",&n,&m);

    int t=;

    for(int i=;i<=m;i++)

    {

        int x,y;scanf("%d%d",&x,&y);

        if(x>y)swap(x,y);

        if(x+!=y)e[++t].x=x,e[t].y=y;

    }

    sort(e+,e+t+,cmp);

    int tot=,p=;

    for(int i=;i<=t;i++)

      if(e[i].x>=p)p=e[i].y,tot++;

    printf("%d",tot+n-);

    return ;

}