ДМ 8

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
2.6 kB
5
Indexable
Never
#include <bits/stdc++.h>
 
#define N 1005
#define sz(x) ((int) ((x).size()))
#define all(x) (x).begin(), (x).end()
 
using namespace std;
 
int main() {
 
    freopen("graph.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    int u, v;
    vector<vector<int>> graph(N);
    while (cin >> u) {
        cin >> v;
        graph[u].push_back(v);
    }
 
    bitset<N> covered;
    vector<int> sub_graphs;
    for (int i = 0; i < N; ++i) { // декомпозиция графа на несколько подграфов
        if (!covered[i]) {
            covered[i] = true;
            sub_graphs.push_back(i);
            for (int j: graph[i]) {
                covered[j] = true;
            }
        }
    }
 
    bitset<N> adjacent; // вершины, в которые есть стрелки из текущего независимого множества
    reverse(all(sub_graphs));
    vector<int> ans = {sub_graphs.front()}; // само независимое множество
    for (int i: graph[sub_graphs.front()]) {
        adjacent[i] = true;
    }
    for (int i = 1; i < sz(sub_graphs); ++i) { // собираем независимые множества из каждого подграфа как в теореме
        if (!adjacent[sub_graphs[i]]) {
            ans.push_back(sub_graphs[i]);
            for (int j: graph[sub_graphs[i]]) {
                adjacent[j] = true;
            }
        }
    }
 
    // Чекер корректности
 
    bitset<N> is; // вершины найденного независимого множества
    for (int i: ans) {
        is[i] = true;
    }
 
    for (int i: ans) {
        for (int j: graph[i]) {
            assert(!is[j] || i == j); // проверяем, что множество действительно независимое (не считая петель)
        }
    }
 
    bitset<N> reached; // вершины, расстояние до которых <= 2 из найденного независимого множества
    for (int i: ans) {
        reached[i] = true;
        for (int j: graph[i]) {
            reached[j] = true; // d = 1
            for (int k: graph[j]) {
                reached[k] = true; // d = 2
            }
        }
    }
 
    for (int i = 0; i < N; ++i) {
        assert(reached[i]); // проверяем, что каждая вершина достижима
    }
 
    for (int i: ans) {
        cout << i << '\n';
    }
 
    return 0;
}
Leave a Comment