长乐 Day 6

今天学习强连通分量和最短路径
最短路还好，基本没问题，那些算法之前学过，比较轻松
但强连通分量炸了
就打———– 1题

这题好不容易才打出来

我花了INT_MAX个h才打出来，这什么强连通很难理解

#include <bits/stdc++.h>
#define L 10005

using namespace std;
int vis[L], a[L], s[L];
int t;
vector<int> g[L];
void dfs(int u) {
    if (not(t - 1))
        return;
    for (int i = 0; i < s[u]; i++) {
        if (not vis[g[u][i]]) {
            vis[g[u][i]] = true;
            if (a[g[u][i]] == 1) {
                t = a[g[u][i]];
                return;
            }
            dfs(g[u][i]);
        }
    }
}
int sum;
bool flag;
int main(void) {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        vis[u] = true, vis[v] = true;
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            flag = true;
            break;
        }
    }
    if (flag) {
        cout << "0";
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end());
        s[i] = unique(g[i].begin(), g[i].end()) - g[i].begin();
    }
    memset(a, -1, sizeof a);
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof vis);
        if (!a[i])
            continue;
        t = -1;
        vis[i] = true;
        dfs(i);
        if (t == 1) {
            a[i] = 1;
            sum++;
        } else if (t == -1) {
            flag = false;
            for (int j = 1; j <= n; j++) {
                if (!vis[j]) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                a[i] = 1;
                sum++;
            } else
                for (int j = 1; j <= n; j++)
                    if (vis[j])
                        a[j] = 0;
        }
    }
    cout << sum;
    return 0;
}

没什么技术含量，看看就好

噫吁嚱，危乎难哉！
强连通之难，难于上青天！