Interesting Graph problem

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

A system contains pods numbered from 1 to pods, distributed across multiple geographical regions. These pods are interconnected by n links, represented by the array connections, such that if two pods are connected directly or indirectly, they belong to the same region.

Each pod has a database connection to which it writes the critical data received. If a pod loses its database connection for some reason, it forwards the data to an active pod in the same region with the lowest ID, and that pod writes the data to the region's database. If there are no active pods left in the region, the data is not written, and an error is recorded in the logs.

Process q queries of two types: a data-sending query of the form "1 pod_id," or a database-connection-failure query of the form "2 pod_id."

For each data-sending query, the program should output the ID of the pod that writes the data to the database. Specifically, when a data-sending query is made to pod sender_pod_id, the program should find the active pod in the same region with the lowest ID and return its ID as the output. If there are no active pods in the region, the program should output -1.

Suppose pods = 3,n = 2 ,connections = [[1, 2], [2, 3]], q = 5, queries = [[2, 2], [1, 2], [2, 1], [2, 3], [1, 1]]. The output for this test case is [1, -1].

#include <iostream> #include <vector> #include <algorithm> #include <set> #include <queue> using namespace std; vector<int> recoverDeadPods(int n, vector<vector<int>> connections, vector<vector<int>> queries) { vector<vector<int>> adj(n+1); for (auto conn : connections) { int u = conn[0]; int v = conn[1]; adj[u].push_back(v); adj[v].push_back(u); } vector<int> region_id(n+1, -1); int region_cnt = 0; vector<set<int>> active_pods; vector<vector<int>> region_pods; // Build regions using BFS for (int i = 1; i <= n; ++i) { if (region_id[i] == -1) { queue<int> q; q.push(i); region_id[i] = region_cnt; vector<int> pods_in_region; set<int> active_in_region; pods_in_region.push_back(i); active_in_region.insert(i); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (region_id[v] == -1) { region_id[v] = region_cnt; q.push(v); pods_in_region.push_back(v); active_in_region.insert(v); } } } region_pods.push_back(pods_in_region); active_pods.push_back(active_in_region); region_cnt++; } } vector<bool> active(n+1, true); vector<int> result; for (auto query : queries) { int type = query[0]; int pod_id = query[1]; if (type == 1) { if (active[pod_id]) { result.push_back(pod_id); } else { int rid = region_id[pod_id]; if (!active_pods[rid].empty()) { result.push_back(*active_pods[rid].begin()); // Get the lowest ID active pod } else { result.push_back(-1); } } } else if (type == 2) { if (active[pod_id]) { active[pod_id] = false; int rid = region_id[pod_id]; active_pods[rid].erase(pod_id); } } } return result; } // Example usage int main() { int n = 2, m = 1, q = 1; vector<vector<int>> connections = {{1, 2}}; vector<vector<int>> queries = {{1, 2}}; vector<int> ans = recoverDeadPods(n, connections, queries); for (int res : ans) { cout << res << endl; } return 0; }

Блог пользователя Gyanendu02