Codeforces 999E(DFS+Tarjan缩点)

Codeforces 999E
题意：给你$n$个点，$m$条边，以及一个初始点$s$，问你至少还需要增加多少条边，使得初始点$s$与剩下其他的所有点都连通。

由于图中可能有环，并且一个环其中一点能到达首都则其他点都可以到达。所以用 Tarjan 对原图缩点然后变成一个 DAG 图。之后统计入度为 0 的点即可，但是要小心从首都出发的链，将这些链先标记，然后每次查找到入度为 0 的点 DFS 看这个点所在链是否全部标记，没有全部标记就可以连一条边到首都。DFS 必要的标记还是要打上qwq，不然 TLE 到死啊

知识点：1 Tarjan小心新图原图区别 2 DFS 必要的标记还是要打上qwq

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;

const int MAXN = 5000 + 5;

int n, m, st;
vector<int> G[MAXN], R[MAXN];
int sz, scc_siz, scc_bl[MAXN], dfn[MAXN], low[MAXN], vis[MAXN];
stack<int> s;
int ino[MAXN], okv[MAXN];

inline void ins(int x, int y) {G[x].push_back(y);}
inline void Rins(int x, int y) {R[x].push_back(y), ino[y]++;}

void tarjan(int u) {
    low[u] = dfn[u] = ++sz, vis[u] = -1, s.push(u);
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) tarjan(v), low[u] = min(low[u], low[v]); 
        else if (vis[v] == -1) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int e;
        scc_siz++;
        do {
            e = s.top(); s.pop();
            scc_bl[e] = scc_siz, vis[e] = 1;
        } while (e != u);
    }
}
void dfs1(int u) {
    okv[u] = 1;
    for (int i = 0; i < (int)R[u].size(); i++) if (!okv[u]) dfs1(R[u][i]); //必要的标记判断还是写上qwq 
}
int dfs2(int u) {
    int ret = okv[u];
    if (!okv[u]) return 0; //必要的标记判断还是写上qwq 
    for (int i = 0; i < (int)R[u].size(); i++) {
        int v = R[u][i];
        if (!okv[v]) return 0; //必要的标记判断还是写上qwq 
        ret &= dfs2(v);
    }
    okv[u] = 1;
    return ret;
}


void clean() {
    ms(ino, 0), ms(vis, 0), ms(okv, 0), sz = scc_siz = 0;
}
int solve() {
    clean();
    for (int x, y, i = 1; i <= m; i++) scanf("%d%d", &x, &y), ins(x, y);
    for (int i = 1; i <= n; i++) if (!vis[i]) tarjan(i);

    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            if (scc_bl[u] != scc_bl[v]) Rins(scc_bl[u], scc_bl[v]);
        }
    }

    dfs1(scc_bl[st]);

    int ans = 0;
    for (int u = 1; u <= scc_siz; u++) if (u != scc_bl[st] && ino[u] == 0 && !dfs2(u)) ans++;

    printf("%d\n", ans);

    return 0; 
}
int main() {
    scanf("%d%d%d", &n, &m, &st), solve();
    return 0;
}