【Day46 LeetCode】图论问题 Ⅳ

一、图论问题 Ⅳ

1、字符串接龙

采用BFS，代码如下：（判断是否在字典中需要遍历每个位置，同时遍历26中可能有点不优雅）

# include<iostream>
# include<string>
# include<vector>
# include<unordered_set>
# include<unordered_map>
# include<queue>

using namespace std;

int main(){
    
    int n;
    cin >> n;
    string src, des, s;
    cin >> src >> des;
    unordered_set<string> dic;
    for(int i=0; i<n; ++i){
        cin >> s;
        dic.insert(s);
    }
    
    queue<string> q;
    q.push(src);
    unordered_map<string, int> mp;
    mp[src] = 1;
    while(!q.empty()){
        string s = q.front(); q.pop();
        int cnt = mp[s];
        // BFS
        for(int i=0; i<s.size(); ++i){
            string ss = s;
            for(int j=0; j<26; ++j){
                ss[i] = 'a' + j;
                if(ss == des){
                    cout << cnt + 1 << endl;
                    return 0;
                }
                if(dic.find(ss) != dic.end() && mp.find(ss)==mp.end()){
                    mp[ss] = cnt+1;
                    q.push(ss);
                }
            }
        }
    }
    cout << 0 << endl;
    return 0;
}

2、有向图的完全可达性

这题和找可达路径的那题不同，因为这题可能存在环，不处理会陷入死循环。所以我们需要标记节点，看是否是已经访问过的，刚好可以复用本来就得用来求解节点是否可达的标记数组。本题需要判断 1节点是否能到所有节点，那么就没有必要回溯去撤销操作了，只要将遍历过的节点都标记上。而搜索路径就需要回溯，不然路径就会混叠在一起。
DFS代码如下：

# include<iostream>
# include<vector>
# include<list>

using namespace std;

void dfs(vector<list<int>> &graph, vector<bool> &visited, int node){
    for(auto nxt : graph[node]){
        if(visited[nxt]==false){
            visited[nxt] = true;
            dfs(graph, visited, nxt);
        }
    }
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<list<int>> graph(n+1);
    while(k--){
        int s, t;
        cin >> s >> t;
        graph[s].push_back(t);
    }
    vector<bool> visited(n+1, false);
    visited[1] = true;
    dfs(graph, visited, 1);
    for(int i=1; i<=n; ++i){
        if(visited[i]==false){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << 1 << endl;
    return 0;
}

BFS版本的代码如下：

# include<iostream>
# include<vector>
# include<list>
# include<queue>

using namespace std;

void bfs(vector<list<int>> &graph, vector<bool> &visited, int node){
    queue<int> q;
    q.push(node);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(auto nxt : graph[cur]){
            if(visited[nxt]==false){
                visited[nxt] = true;
                q.push(nxt);
            }
        }
    }
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<list<int>> graph(n+1);
    while(k--){
        int s, t;
        cin >> s >> t;
        graph[s].push_back(t);
    }
    vector<bool> visited(n+1, false);
    visited[1] = true;
    bfs(graph, visited, 1);
    for(int i=1; i<=n; ++i){
        if(visited[i]==false){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << 1 << endl;
    return 0;
}

3、岛屿周长

周长是由边组成的，什么是能构成周长的边？陆地与水域接壤的部分。所以可以通过查看陆地是否存在水域(超出边界也是水域)，每存在一个水域+1，表示一条有效的边，能给周长+1。代码如下：

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>(m));
    for(int i=0; i<n; ++i)
        for(int j=0; j<m; ++j)
            cin >> graph[i][j];
    
    int ans = 0;
    vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j){
            if(graph[i][j]==1){
                for(auto xy : dirs){
                    int x = i + xy[0], y = j + xy[1];
                    if(x<0 || x>=n || y<0 || y>=m || graph[x][y]==0)
                        ++ans;
                }   
            }
        }
    }

    cout << ans << endl;
    return 0;
}