第 4 章 图论

// 存图 + BFS：用 vector 邻接表存无向图，BFS 求 1 号点到每个点最少要走几条边。
// 输入：n m，接着 m 行 u v（无向边，可能有重边、自环）。输出：n 个数，走不到的点输出 -1。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];  // adj[u] 里存 u 的所有邻居
int dist[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // 无向边要存两次：u 能到 v，v 也能到 u
        adj[v].push_back(u);
    }
    memset(dist, -1, sizeof(dist));  // -1 表示还没到过，同时充当“访问标记”
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] != -1) continue;  // 到过的点不再处理；第一次到达时的步数就是最少的
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
    for (int i = 1; i <= n; i++) cout << dist[i] << " \n"[i == n];
    return 0;
}

bool vis[N];
void dfs(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs(v);
}

const int N = 100005, M = 200005;  // 无向图：M 要开到边数的两倍
int head[N], nxt[M], to[M], tot;   // head[u]：u 的第一条边的编号；nxt[i]：和第 i 条边同起点的下一条边

void add(int u, int v) {           // 加一条 u->v 的边。无向边要调用两次：add(u, v), add(v, u)
    to[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
}

for (int i = head[u]; i; i = nxt[i]) {  // 遍历 u 的所有出边
    int v = to[i];
}

// Dijkstra（堆优化）：边权非负的单源最短路。洛谷 P4779 的格式。
// 输入：n m s，接着 m 行 u v w（有向边 u->v，长度 w）。输出：s 到每个点的最短距离，走不到输出 -1（P4779 保证都能走到）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;              // (距离, 点)。距离放前面，堆才会按距离比较
const int N = 100005;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;    // 约 4.5e18，比任何真实距离都大；两个 INF 相加也不会超出 long long
vector<pair<int, int>> adj[N];          // adj[u] 里存 (v, w)
ll dist[N];                             // 距离一律 long long
bool done[N];                           // done[u]：u 的最短距离已经确定

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    memset(dist, 0x3f, sizeof(dist));   // 每个字节填 0x3f，得到的正好是上面的 INF
    priority_queue<pli, vector<pli>, greater<pli>> pq;  // 小根堆：堆顶是距离最小的
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (done[u]) continue;          // 同一个点可能入堆多次，只处理距离最小的那一次
        done[u] = true;
        for (auto &e : adj[u]) {
            int v = e.first, w = e.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    for (int i = 1; i <= n; i++) cout << (dist[i] == INF ? -1 : dist[i]) << " \n"[i == n];
    return 0;
}

// Floyd：所有点对之间的最短路，点数不超过 500 时可用。洛谷 B3647 的格式。
// 输入：n m，接着 m 行 u v w（无向边，可能有重边）。
// 输出：n 行 n 列，第 i 行第 j 个数是 i 到 j 的最短距离，走不到输出 -1。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 505;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll d[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j) ? 0 : INF;  // 自己到自己是 0，其余先当作走不到
    for (int i = 1; i <= m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);  // 有重边时只留最短的一条，所以用 min 而不是直接赋值
        d[v][u] = min(d[v][u], w);
    }
    for (int k = 1; k <= n; k++)            // k 必须在最外层：它表示“现在允许用 1..k 号点中转”
        for (int i = 1; i <= n; i++) {
            if (d[i][k] == INF) continue;   // i 走不到 k，拿 k 中转没有意义
            for (int j = 1; j <= n; j++)
                if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cout << (d[i][j] == INF ? -1 : d[i][j]) << " \n"[j == n];
    return 0;
}

for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        for(int k=1;k<=n;k++){          // 错：中转点 k 在最内层
            sp[i][j]=min(sp[i][j],sp[i][k]+sp[j][k]);
            sp[j][i]=sp[i][j];
        }
    }
}

for(int k=1;k<=n;k++){                  // 对：中转点 k 在最外层
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            sp[i][j]=min(sp[i][j],sp[i][k]+sp[j][k]);
            sp[j][i]=sp[i][j];
        }
    }
}

// SPFA（用队列优化的 Bellman-Ford）：边权可以是负数，还能发现负环。洛谷 P3385 的格式。
// 输入：T 组数据。每组先是 n m，接着 m 行 u v w：w>=0 表示双向边，w<0 表示只有 u->v 这一个方向。
// 输出：每组一行，从 1 号点出发能走到负环输出 YES，否则输出 NO。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2005;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
vector<pair<int, int>> adj[N];
ll dist[N];
int cnt[N];   // cnt[v]：当前记录的 1 到 v 的最短路上有几条边
bool inq[N];  // inq[v]：v 此刻是否在队列里

bool has_negative_cycle(int n) {
    for (int i = 1; i <= n; i++) dist[i] = INF, cnt[i] = 0, inq[i] = false;
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    inq[1] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (auto &e : adj[u]) {
            int v = e.first, w = e.second;
            if (dist[u] + w >= dist[v]) continue;
            dist[v] = dist[u] + w;
            cnt[v] = cnt[u] + 1;
            if (cnt[v] >= n) return true;  // 没有负环时最短路最多 n-1 条边；到了 n 条说明在绕负环
            if (!inq[v]) {                 // 已经在队列里就不用重复放
                q.push(v);
                inq[v] = true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) adj[i].clear();  // 多组数据：上一组的边必须清掉
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            adj[u].push_back({v, w});
            if (w >= 0) adj[v].push_back({u, w});
        }
        cout << (has_negative_cycle(n) ? "YES" : "NO") << '\n';
    }
    return 0;
}

// 最短路计数：无权图上，1 号点到每个点有多少条不同的最短路。洛谷 P1144 的格式。
// 输入：n m，接着 m 行 u v（无向边，可能有重边、自环）。
// 输出：n 行，第 i 行是 1 到 i 的最短路条数对 100003 取模的结果，走不到输出 0。
#include <bits/stdc++.h>
using namespace std;

const int N = 1000005, MOD = 100003;
vector<int> adj[N];
int dist[N], ways[N];  // ways[v]：1 到 v 的最短路条数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[1] = 0;
    ways[1] = 1;  // 起点到自己算 1 条
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {  // 第一次到 v：最短距离确定，入队
                dist[v] = dist[u] + 1;
                q.push(v);
            }
            if (dist[v] == dist[u] + 1)  // u 是 v 的“上一层”：经过 u 的最短路都能接上这条边到 v
                ways[v] = (ways[v] + ways[u]) % MOD;
        }
    }
    for (int i = 1; i <= n; i++) cout << ways[i] << '\n';
    return 0;
}

if (dist[u] + w < dist[v]) {          // 找到更短的路：条数整个换掉
    dist[v] = dist[u] + w;
    ways[v] = ways[u];
    pq.push({dist[v], v});
} else if (dist[u] + w == dist[v]) {  // 找到一样短的路：条数累加
    ways[v] = (ways[v] + ways[u]) % MOD;
}

int uu=u,uuu=u,m=0;
while(uu<n){
    uuu=uu;uu=ft[uu];m++;
    for(int i=uuu+1;i<=uu;i++) dis[u][i]=m;
}

// 并查集：合并两个集合，询问两个元素是否在同一个集合。洛谷 P3367 的格式。
// 输入：n m，接着 m 行 z x y：z=1 合并 x 和 y 所在的集合；z=2 询问 x 和 y 是否在同一集合，是输出 Y，否输出 N。
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
int fa[N], sz[N];  // fa[x]：x 的父亲，根的父亲是自己；sz[x]：以 x 为根的集合有多少个元素（只有根的值有意义）

int find(int x) {  // 找 x 所在集合的根，顺手把路上的点直接挂到根下面（路径压缩）
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);       // 合并的是两个根，不是 x 和 y 本身
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);  // 小集合挂到大集合下面，树不会太深
    fa[y] = x;
    sz[x] += sz[y];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;  // 一开始每个元素自成一个集合
    while (m--) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1) unite(x, y);
        else cout << (find(x) == find(y) ? "Y" : "N") << '\n';
    }
    return 0;
}

// 扩展域并查集：维护“同类 / 异类”两种关系，并能发现矛盾。
// 输入：n m，接着 m 行 t u v：t=1 声称 u、v 同类；t=2 声称 u、v 异类；t=3 询问 u、v 的关系。
// 输出：对声明——与之前接受的声明不矛盾就接受，输出 YES；矛盾就丢弃，输出 NO。
//       对询问——输出 SAME（同类）、DIFF（异类）或 UNKNOWN（现在还推不出来）。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int fa[2 * N];  // 点 x 代表“x 本身”，点 x+n 代表“x 的对立面”。两个点在同一集合里，表示它们一定同类

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = find(y); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;  // 注意是 2n 个点
    while (m--) {
        int t, u, v;
        cin >> t >> u >> v;
        bool same = find(u) == find(v);      // 已经能推出 u、v 同类
        bool diff = find(u) == find(v + n);  // 已经能推出 u、v 异类（u 和“v 的对立面”同类）
        if (t == 3) {
            cout << (same ? "SAME" : diff ? "DIFF" : "UNKNOWN") << '\n';
        } else if (t == 1) {
            if (diff) {
                cout << "NO\n";
                continue;
            }
            unite(u, v), unite(u + n, v + n);  // 本身和本身合并，对立面和对立面合并
            cout << "YES\n";
        } else {
            if (same) {
                cout << "NO\n";
                continue;
            }
            unite(u, v + n), unite(u + n, v);  // u 和 v 的对立面同类，反过来也一样
            cout << "YES\n";
        }
    }
    return 0;
}

int fa[N], rel[N];           // rel[x]：x 与它父亲的关系，0 同类，1 异类
int find(int x) {
    if (fa[x] == x) return x;
    int root = find(fa[x]);  // 先让父亲直接挂到根下面，这时 rel[fa[x]] 已经是“父亲与根的关系”
    rel[x] ^= rel[fa[x]];    // x 与根的关系 = x 与父亲的关系 异或 父亲与根的关系
    return fa[x] = root;
}
// 声明 u、v 的关系是 want（0 同类，1 异类）：
int ru = find(u), rv = find(v);
if (ru == rv) { /* 已有结论 rel[u] ^ rel[v]，与 want 不同就是矛盾 */ }
else fa[ru] = rv, rel[ru] = rel[u] ^ rel[v] ^ want;

// Kruskal：最小生成树。洛谷 P3366 的格式。
// 输入：n m，接着 m 行 x y z（无向边，长度 z）。输出：最小生成树的边权之和；图不连通输出 orz。
#include <bits/stdc++.h>
using namespace std;

const int N = 5005, M = 200005;
struct Edge {
    int u, v, w;
} e[M];
int fa[N];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1, e + m + 1, cmp);  // 所有边按长度从小到大排
    for (int i = 1; i <= n; i++) fa[i] = i;
    long long total = 0;
    int used = 0;  // 已经选了几条边
    for (int i = 1; i <= m && used < n - 1; i++) {
        int x = find(e[i].u), y = find(e[i].v);
        if (x == y) continue;  // 两端已经连通，再加这条边会成环，跳过
        fa[x] = y;
        total += e[i].w;
        used++;
    }
    if (used < n - 1) cout << "orz\n";  // 选不够 n-1 条边，说明图不连通
    else cout << total << '\n';
    return 0;
}

// 拓扑排序（Kahn 算法）+ DAG 上的 DP：判断有向图有没有环；没有环时，求最长的一条路径上有几个点。
// 输入：n m，接着 m 行 u v（有向边 u->v，表示 u 必须排在 v 前面）。输出：有环输出 -1，否则输出最长路径上的点数。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int indeg[N], f[N];  // indeg[v]：v 还有几个前驱没处理完；f[v]：以 v 结尾的最长路径上的点数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i), f[i] = 1;  // 没有前驱的点可以最先处理
    vector<int> order;  // 出队的顺序就是一个拓扑序
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            f[v] = max(f[v], f[u] + 1);      // u 出队时 f[u] 已经是最终值，可以放心用来更新后继
            if (--indeg[v] == 0) q.push(v);  // v 的前驱全部处理完了，轮到 v
        }
    }
    if ((int)order.size() < n) {  // 有点始终没能入队：它在环上，或者排在环的后面
        cout << "-1\n";
        return 0;
    }
    cout << *max_element(f + 1, f + n + 1) << '\n';
    return 0;
}

// 二分图判定：能不能把所有点染成黑白两色，使每条边的两端颜色不同。用 BFS 染色。
// 输入：n m，接着 m 行 u v（无向边）。输出：是二分图输出 YES，否则输出 NO。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> adj[N];
int color[N];  // 0 表示还没染色，1 和 2 是两种颜色

bool paint(int s) {  // 给 s 所在的连通块染色，发现矛盾返回 false
    queue<int> q;
    color[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (color[v] == color[u]) return false;  // 一条边两端同色：图里有奇数长度的环
            if (color[v] == 0) {
                color[v] = 3 - color[u];             // 1 变 2，2 变 1
                q.push(v);
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bool ok = true;
    for (int i = 1; i <= n && ok; i++)  // 图可能不连通，每个连通块都要染一遍
        if (color[i] == 0) ok = paint(i);
    cout << (ok ? "YES" : "NO") << '\n';
    return 0;
}

// Tarjan 求强连通分量，缩点后在 DAG 上 DP。洛谷 P3387 的格式。
// 输入：n m，n 个点权，接着 m 行 u v（有向边）。
// 输出：选一条路径（点和边都可以重复走，但每个点的点权只算一次），点权之和最大是多少。
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
vector<int> adj[N], dag[N];        // dag：缩点之后的图，结点是分量编号
int a[N], dfn[N], low[N], timer;   // dfn[u]：u 是第几个被访问的；low[u]：u 往下走能绕回到的最早的点的 dfn
int stk[N], top;                   // 栈里是“访问过、但还没归入任何分量”的点
bool in_stk[N];
int scc[N], scc_cnt;               // scc[u]：u 属于第几个强连通分量
long long sum[N], f[N];            // sum[c]：分量 c 里的点权和；f[c]：从分量 c 出发能拿到的最大点权和

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u, in_stk[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {    // v 还在栈里，说明从 u 能绕回 v
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] != dfn[u]) return;  // u 还能绕回更早的点，它不是分量的“入口”
    scc_cnt++;                     // 栈里从 u 往上的所有点，恰好构成一个强连通分量
    int v;
    do {
        v = stk[top--];
        in_stk[v] = false;
        scc[v] = scc_cnt;
        sum[scc_cnt] += a[v];
    } while (v != u);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);    // 图可能不连通，每个没访问过的点都要当一次起点
    for (int u = 1; u <= n; u++)
        for (int v : adj[u])
            if (scc[u] != scc[v]) dag[scc[u]].push_back(scc[v]);  // 跨分量的边留下，分量内部的边丢掉
    long long ans = 0;
    for (int c = 1; c <= scc_cnt; c++) {  // 若有边 c->d，则 d 的编号一定比 c 小，所以从小到大算就是合法的 DP 顺序
        f[c] = sum[c];
        for (int d : dag[c]) f[c] = max(f[c], sum[c] + f[d]);
        ans = max(ans, f[c]);
    }
    cout << ans << '\n';
    return 0;
}

// Tarjan 求割边（桥）：删掉这条边，图的连通块会变多。图里有重边、自环也能正确处理。
// 输入：n m，接着 m 行 u v（无向边）。
// 输出：第一行是割边的条数；之后每行一条割边 u v（u<v），按 u、v 从小到大排列。
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<pair<int, int>> adj[N];  // (邻居, 边的编号)。记编号是为了区分“来时走的那条边”和“另一条重边”
int dfn[N], low[N], timer;      // low[u]：u 和它的子树不走来时的边，能到达的最早的点的 dfn
vector<pair<int, int>> bridges;

void tarjan(int u, int from_edge) {  // from_edge：从父亲走到 u 用的那条边的编号
    dfn[u] = low[u] = ++timer;
    for (auto &e : adj[u]) {
        int v = e.first, id = e.second;
        if (id == from_edge) continue;  // 不许沿着来时的那条边原路返回；重边的编号不同，可以走
        if (!dfn[v]) {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])        // v 那一侧无论如何绕不回 u 或更早的点：这条边是唯一的通道
                bridges.push_back({min(u, v), max(u, v)});
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);  // 图可能不连通
    sort(bridges.begin(), bridges.end());
    cout << (int)bridges.size() << '\n';
    for (auto &b : bridges) cout << b.first << ' ' << b.second << '\n';
    return 0;
}