27.6 แบบฝึกหัด

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
int heard_on[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    fill(heard_on, heard_on + n + 1, -1);
    queue<int> waiting;
    heard_on[s] = 0;
    waiting.push(s);
    int heard = 0, last_day = 0;
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        heard++;
        last_day = heard_on[v];
        for (int next : adj[v]) {
            if (heard_on[next] == -1) {
                heard_on[next] = heard_on[v] + 1;
                waiting.push(next);
            }
        }
    }
    cout << heard << ' ' << last_day << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int r = 0; r < rows; r++) {
        cin >> grid[r];
    }
    vector<vector<bool>> seen(rows, vector<bool>(cols, false));
    int islands = 0, largest = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] != '#' || seen[r][c]) {
                continue;
            }
            int cells = 0;
            bool on_edge = false;
            queue<pair<int, int>> waiting;
            seen[r][c] = true;
            waiting.push({r, c});
            while (!waiting.empty()) {
                auto [cr, cc] = waiting.front();
                waiting.pop();
                cells++;
                if (cr == 0 || cr == rows - 1 || cc == 0 || cc == cols - 1) {
                    on_edge = true;
                }
                for (int d = 0; d < 4; d++) {
                    int nr = cr + dr[d];
                    int nc = cc + dc[d];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '#' && !seen[nr][nc]) {
                        seen[nr][nc] = true;
                        waiting.push({nr, nc});
                    }
                }
            }
            if (!on_edge) {
                islands++;
                largest = max(largest, cells);
            }
        }
    }
    cout << islands << ' ' << largest << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
bool seen[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int no_loop = 0, ring = 0;
    for (int start = 1; start <= n; start++) {
        if (seen[start]) {
            continue;
        }
        long long villages = 0, road_ends = 0;
        bool all_two = true;
        stack<int> waiting;
        seen[start] = true;
        waiting.push(start);
        while (!waiting.empty()) {
            int v = waiting.top();
            waiting.pop();
            villages++;
            road_ends += adj[v].size();
            if (adj[v].size() != 2) {
                all_two = false;
            }
            for (int next : adj[v]) {
                if (!seen[next]) {
                    seen[next] = true;
                    waiting.push(next);
                }
            }
        }
        if (road_ends / 2 == villages - 1) {
            no_loop++;
        } else if (all_two) {
            ring++;
        }
    }
    cout << no_loop << ' ' << ring << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
int rows, cols;
vector<string> grid;

int steps_between(char from, char to)
{
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    queue<pair<int, int>> waiting;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == from) {
                dist[r][c] = 0;
                waiting.push({r, c});
            }
        }
    }
    while (!waiting.empty()) {
        auto [r, c] = waiting.front();
        waiting.pop();
        if (grid[r][c] == to) {
            return dist[r][c];
        }
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                waiting.push({nr, nc});
            }
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> rows >> cols;
    grid.resize(rows);
    for (int r = 0; r < rows; r++) {
        cin >> grid[r];
    }
    int first = steps_between('S', 'P');
    int second = steps_between('P', 'E');
    if (first == -1 || second == -1) {
        cout << -1 << '\n';
    } else {
        cout << first + second << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> out_roads[MAXN];
vector<int> in_roads[MAXN];

// รับอาเรย์ของ vector แบบเดียวกับส่งอาเรย์เข้าฟังก์ชันในหน้า 8.3 ฟังก์ชันใช้ตัวจริง ไม่ได้คัดลอก
vector<bool> reachable(int n, vector<int> roads[])
{
    vector<bool> seen(n + 1, false);
    queue<int> waiting;
    seen[1] = true;
    waiting.push(1);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        for (int next : roads[v]) {
            if (!seen[next]) {
                seen[next] = true;
                waiting.push(next);
            }
        }
    }
    return seen;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        out_roads[from].push_back(to);
        in_roads[to].push_back(from);
    }
    vector<bool> go = reachable(n, out_roads);
    vector<bool> back = reachable(n, in_roads);
    int go_count = 0, back_count = 0, both = 0;
    for (int v = 2; v <= n; v++) {
        go_count += go[v]; // true บวกเป็น 1 false บวกเป็น 0
        back_count += back[v];
        both += go[v] && back[v];
    }
    cout << go_count << ' ' << back_count << ' ' << both << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
int team[MAXN];
char registered[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0; i < k; i++) {
        int v;
        char color;
        cin >> v >> color;
        registered[v] = color;
    }
    fill(team, team + n + 1, -1);
    int red = 0;
    for (int start = 1; start <= n; start++) {
        if (team[start] != -1) {
            continue;
        }
        int side_size[2] = {0, 0};
        int red_side = -1;
        queue<int> waiting;
        team[start] = 0;
        waiting.push(start);
        while (!waiting.empty()) {
            int v = waiting.front();
            waiting.pop();
            side_size[team[v]]++;
            if (registered[v] != 0) {
                int need = (registered[v] == 'R' ? team[v] : 1 - team[v]);
                if (red_side == -1) {
                    red_side = need;
                } else if (red_side != need) {
                    cout << -1 << '\n';
                    return 0;
                }
            }
            for (int next : adj[v]) {
                if (team[next] == -1) {
                    team[next] = 1 - team[v];
                    waiting.push(next);
                } else if (team[next] == team[v]) {
                    cout << -1 << '\n';
                    return 0;
                }
            }
        }
        if (red_side == -1) {
            red += min(side_size[0], side_size[1]);
        } else {
            red += side_size[red_side];
        }
    }
    cout << red << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
int dist[MAXN];
int owner[MAXN];
int served[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> branches(k);
    for (int i = 0; i < k; i++) {
        cin >> branches[i];
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    fill(dist, dist + n + 1, -1);
    queue<int> waiting;
    for (int b : branches) {
        dist[b] = 0;
        owner[b] = b;
        waiting.push(b);
    }
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        served[owner[v]]++;
        for (int next : adj[v]) {
            if (dist[next] == -1) {
                dist[next] = dist[v] + 1;
                owner[next] = owner[v];
                waiting.push(next);
            } else if (dist[next] == dist[v] + 1 && owner[v] < owner[next]) {
                owner[next] = owner[v];
            }
        }
    }
    for (int i = 0; i < k; i++) {
        cout << served[branches[i]] << (i + 1 == k ? '\n' : ' ');
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200001;
vector<int> adj[MAXN];
int to_goal[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, start, goal;
    cin >> n >> m >> start >> goal;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    fill(to_goal, to_goal + n + 1, -1);
    queue<int> waiting;
    to_goal[goal] = 0;
    waiting.push(goal);
    while (!waiting.empty()) {
        int v = waiting.front();
        waiting.pop();
        for (int next : adj[v]) {
            if (to_goal[next] == -1) {
                to_goal[next] = to_goal[v] + 1;
                waiting.push(next);
            }
        }
    }
    if (to_goal[start] == -1) {
        cout << -1 << '\n';
        return 0;
    }
    cout << to_goal[start] << '\n';
    int v = start;
    cout << v;
    while (v != goal) {
        int best = -1;
        for (int next : adj[v]) {
            if (to_goal[next] == to_goal[v] - 1 && (best == -1 || next < best)) {
                best = next;
            }
        }
        v = best;
        cout << ' ' << v;
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    map<string, int> moves;
    queue<string> waiting;
    moves["123456780"] = 0;
    waiting.push("123456780");
    while (!waiting.empty()) {
        string board = waiting.front();
        waiting.pop();
        size_t blank = board.find('0');
        int r = blank / 3, c = blank % 3;
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) {
                continue;
            }
            string next = board;
            swap(next[blank], next[nr * 3 + nc]);
            if (moves.count(next) == 0) {
                moves[next] = moves[board] + 1;
                waiting.push(next);
            }
        }
    }
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string board;
        cin >> board;
        auto it = moves.find(board);
        cout << (it == moves.end() ? -1 : it->second) << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows, cols;
    cin >> rows >> cols;
    vector<string> grid(rows);
    for (int r = 0; r < rows; r++) {
        cin >> grid[r];
    }
    vector<vector<int>> cuts(rows, vector<int>(cols, INT_MAX));
    deque<pair<int, int>> waiting;
    int goal_r = 0, goal_c = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 'S') {
                cuts[r][c] = 0;
                waiting.push_back({r, c});
            } else if (grid[r][c] == 'E') {
                goal_r = r;
                goal_c = c;
            }
        }
    }
    while (!waiting.empty()) {
        auto [r, c] = waiting.front();
        waiting.pop_front();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == '#') {
                continue;
            }
            int cost = (grid[nr][nc] == 'T' ? 1 : 0);
            if (cuts[r][c] + cost < cuts[nr][nc]) {
                cuts[nr][nc] = cuts[r][c] + cost;
                if (cost == 0) {
                    waiting.push_front({nr, nc});
                } else {
                    waiting.push_back({nr, nc});
                }
            }
        }
    }
    int answer = cuts[goal_r][goal_c];
    cout << (answer == INT_MAX ? -1 : answer) << '\n';
    return 0;
}