贴个原题

在二维空间中给定一定数量的线段，线段的右端点的横坐标必然比左端点的横坐标大。第一行输入n（n < 10000），表示一共有n条线段。之后输入n行，每一行依次输入左端点的横、纵坐标，右端点的横、纵坐标；一些线段可以连在一起，规定连接的规则只能是一条线段的左端点和另一条线段的右端点相连，要求输出连在一起的大线段最多有多少条线段，以及最大线段起点（左端点）的横、纵坐标。输入的数据规模不会超过int型变量范围。

测试用例1：
输入：
1
1 2 2 3

输出：
1 1 2

测试用例2：
输入：
4
1 2 2 3
2 3 3 4
3 4 4 1
2 3 5 6

输出：
3 1 2

下面给给出两种实现：

DP

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Segment {
    int x1, y1, x2, y2;
    Segment(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {}
};

int main() {
    int n;
    cin >> n;
    vector<Segment> segments;

    // 输入线段数据
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segments.emplace_back(x1, y1, x2, y2);
    }

    // 按照左端点排序，方便后续查找
    sort(segments.begin(), segments.end(), [](const Segment &a, const Segment &b) {
        return a.x1 < b.x1 || (a.x1 == b.x1 && a.y1 < b.y1);
    });

    // 动态规划数组
    vector<int> dp(n, 1); // dp[i] 表示以第 i 个线段结尾的最长链条长度; 每条线段的初始长度为1
    vector<int> startIndex(n); // startIndex[i] 记录以第 i 个线段结尾的最长链条的起始线段索引

    for (int i = 0; i < n; ++i) {
        startIndex[i] = i; // 初始化为每条线段自身
    }

    int maxLen = 1; // 记录最长链条的长度
    int bestStart = 0; // 记录最长链条的起点

    // 动态规划计算最长链条
    for (int i = 1; i < n; ++i) { // 外层循环遍历所有的线段，从第二条线段（i = 1）开始
        for (int j = 0; j < i; ++j) { //用于检查这些线段是否能够连接到当前的第 i 条线段。
            if (segments[j].x2 == segments[i].x1 && segments[j].y2 == segments[i].y1) {
                if (dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    startIndex[i] = startIndex[j]; // 更新起点索引
                }
            }
        }
        // 如果找到更长的链条，更新最长链条信息
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            bestStart = startIndex[i];
        }
    }

    // 输出结果
    cout << maxLen << " " << segments[bestStart].x1 << " " << segments[bestStart].y1 << endl;

    return 0;
}

dfs

#include <cstdio> 
#include <algorithm> 
#include <cstring> 

using namespace std; 

const int maxn = 10010; 

int cnt[maxn], temp = 0; 
int n, s, t; 

struct line { 
    int sx, sy, tx, ty; 
}l[maxn]; 

// 关键代码
void check(int i, int now) 
{ //对线段 i 进行讨论，查看 now 之后的线段是否与线段i重合 
    for(int j = now + 1; j < n; j++) 
    { 
        if(l[j].sx == l[now].tx && l[j].sy == l[now].ty) 
        { //若此时重合 
            temp++; 
            check(i, j); 
            temp--; 
        } 

        else if(l[j].sx > l[now].tx) // 判断当前点的左端点横坐标是否大于上一个点右端点的横坐标
        { //因已按横坐标排序，此句用于加速判断，可以不写 
            return; 
        } 
    } 
    //当未找到退出循环后，比较temp和对i的计数器，若更大则赋值 
    //虽然每次从check退出都会判断一下，但是如果开flag标记找到，也会判断一下所以就这样吧 
    if(temp > cnt[i]) cnt[i] = temp; 
    return; 
} 

bool cmp(line a, line b) 
{ 
    return a.sx < b.sx; 
} 

int main() 
{ 
    scanf("%d", &n); 
    for(int i = 0; i < n; i++) 
    { 
        scanf("%d%d%d%d", &l[i].sx, &l[i].sy, &l[i].tx, &l[i].ty); 
    } 
    sort(l, l + n, cmp); //对所有线段按起点横坐标从小到大排序 
    memset(cnt, 0, sizeof(cnt));

    for(int i = 0; i < n; i++) 
    { 
        check(i, i); 
    } 
    int MAX = -1, num; 
    for(int i = 0; i < n; i++) 
    { 
        if(cnt[i] > MAX) 
        { 
            MAX = cnt[i]; 
            num = i; 
        } 
    } 
    printf("%d %d %d\n", MAX + 1, l[num].sx, l[num].sy); 
    return 0; 
}