CodeForces770C【强连通分量+DFS序】

最新推荐文章于 2024-02-26 16:58:33 发布

keyboarder_zsq

最新推荐文章于 2024-02-26 16:58:33 发布

阅读量698

点赞数

分类专栏： codeforces DFS 文章标签： codeforces dfs

本文链接：https://blog.csdn.net/KEYboarderQQ/article/details/78617796

版权

博客详细解释了CodeForces770C问题的解决策略，首先指出常规建图方法不适用，然后提出通过建立u到v[]的边来构造图。接着，利用Tarjan算法检测强连通分量以判断是否存在不满足条件的环。在失败后，博主采用了针对每个main课程的DFS搜索方法，意外发现拓扑排序的逆序等同于DFS序。虽然代码可能较为粗糙，但思路与题解相似。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

思路：
显然按照他的意思建图肯定不行。
对于u所需要先解决的v[], 建边 u -> v[], 然后就是判断一下每个main 课程是否在一个环里，或者是不是他需要先修的课程在环里，这样子就不满足。
然后我就很爆炸，窝很蠢地想到了Tarjan，然后就处理了一下那些强连通分量，然后就是用来判断是不是在环里，不满足。
然后就是对每个main 课程 DFS搜，然后就好啦，然后智障的窝第一次发现这个拓扑排序的逆序竟然是DFS序。。。
因为菜啊！！不会一次DFS就能判断= =、就瞄了瞄题解。。我就不多bb了…思路基本一样。。。但是人家的写法。。(窝看到的时候内心是崩溃的)

void dfs(int u) {
    if (color[u] == 0) {
        color[u] = 1;
        for (int to: g[u])
            dfs(to);
        color[u] = 2;
        ord.push_back(u);
    } else if (color[u] == 1)
        cycle = true;
}

然后我的搓代码。。(其实单组案例可以去掉那些没必要的初化)

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<list>
using namespace std;

typedef pair<int,int> PII;
typedef long long LL;

#define mem(a, b) memset(a, b

最低0.47元/天解锁文章