Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <climits>
- #include <iostream>
- #include <memory>
- #include <vector>
- using namespace std;
- /*
- дфс с функцией топ сорта (делает нужный порядок вершин)
- - из каждой - прошли и сделали порядок
- прошли в обратном порядке,
- посчитали scc сильной связности (дфс по конденсации графа = по компонентам)
- */
- void Dfs1(int u, vector<vector<int>>& edges, vector<bool>& is_visited, vector<int>& order) {
- is_visited[u] = true;
- for (int v : edges[u]) {
- if (is_visited[v]) continue;
- Dfs1(v, edges, is_visited, order);
- }
- order.push_back(u);
- }
- void Dfs2(int u, vector<vector<int>>& t_edges, vector<bool>& is_visited, vector<int>& component) {
- is_visited[u] = true;
- component.push_back(u);
- for (int v : t_edges[u]) {
- if (is_visited[v]) continue;
- Dfs2(v, t_edges, is_visited, component);
- }
- }
- int main() {
- int n, e;
- cin >> n >> e;
- vector<vector<int>> edges(n);
- vector<vector<int>> t_edges(n);
- for (int i = 0; i < e; ++i) {
- int u, v;
- cin >> u >> v;
- --u;
- --v;
- edges[u].push_back(v);
- t_edges[v].push_back(u);
- }
- vector<int> order;
- vector<bool> is_visited(n, false);
- for (int u = 0; u < n; ++u) {
- if (is_visited[u]) continue;
- Dfs1(u, edges, is_visited, order);
- }
- for (int i = 0; i < n; i++) {
- is_visited[i] = 0;
- }
- vector<vector<int>> all_component;
- vector<int> component;
- reverse(order.begin(), order.end());
- for (int i = 0; i < n; i++) {
- int u = order[i];
- if (is_visited[u]) continue;
- Dfs2(u, t_edges, is_visited, component);
- all_component.push_back(component);
- component.clear();
- }
- vector<int> compr(n);
- vector<int> min_numbers_houses_from_every_family(n, INT_MAX);
- for (int i = 0; i < all_component.size(); ++i) {
- for (auto v : all_component[i]) {
- compr[v] = i;
- }
- }
- return 0;
- }
- /*
- test1
- 5 6
- 1 4
- 1 5
- 2 3
- 3 2
- 4 3
- 5 1
- 3 2
- 1 4
- 4 2
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement