您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 1181 變形課：多種解法的圖連通性問題

編輯：C++ 入門

HDU 1181 變形課：多種解法的圖連通性問題

這道題被稱為「水題」，核心任務是判斷在有向圖中，是否存在從'B'開頭的單詞鏈到達'M'結尾的單詞。可用DFS、BFS、並查集、最短路（SPFA）等多種方法求解。

問題建模

將每個單詞視為一條有向邊：起點為首字母，終點為尾字母。26個字母構成頂點集。輸入以'0'結束一組測試數據，多組測試連續輸入。

SPFA最短路解法

作者採用SPFA檢測從頂點1('B')到頂點12('M')是否可達：

#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
#include <iostream>
#define INF 0x7fffffff
#define SIZE 30
using namespace std;

struct Edge { int v, len; };
vector<Edge> g[SIZE];

void SPFA() {
    int dis[SIZE]; bool vis[SIZE];
    for (int i = 0; i < 26; i++) { dis[i] = INF; vis[i] = 0; }
    dis[1] = 0; vis[1] = 1;
    queue<int> q; q.push(1);
    
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = 0;
        for (auto &e : g[u]) {
            int v = e.v, len = e.len;
            if (dis[v] > dis[u] + len) {
                dis[v] = dis[u] + len;
                if (!vis[v]) { vis[v] = 1; q.push(v); }
            }
        }
    }
    if (dis[12] == INF) puts("No.");
    else puts("Yes.");
}

int main() {
    char str[101];
    while (~scanf("%s", str)) {
        if (str[0] == '0') {
            SPFA();
            for (int i = 0; i < 26; i++) g[i].clear();
        } else {
            int len = strlen(str) - 1;
            Edge now; now.v = str[len] - 'a'; now.len = 1;
            g[str[0] - 'a'].push_back(now);
        }
    }
}