#include <iostream> #include <vector> #include <algorithm> #include <set> #include <cstring> #include <cassert> using namespace std; struct sc { int s; int ip; bool full; sc(int a, int b, bool c) : s(a), ip(b), full(c) {} }; int n, m, k; bool odw[200001]; vector<sc> s[200001]; vector<pair<int, int>> kraw, flip; vector<int> vodw; long long wynik[51]; int dfs(int a) { if (odw[a]) return 0; int udalosie = 0, gdzie = 0; odw[a] = 1; vodw.push_back(a); for (int i = 0; i < (int)s[a].size(); i++) { if (s[a][i].full || odw[s[a][i].s]) continue; if (s[a][i].s == 0 || dfs(s[a][i].s)) { udalosie = 1; gdzie = i; break; } } if (udalosie) { int i = gdzie; s[a][i].full = true; flip.emplace_back(a, i); if (s[a][i].ip != -1) { s[s[a][i].s][s[a][i].ip].full = false; flip.emplace_back(s[a][i].s, s[a][i].ip); } } return udalosie; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; kraw.emplace_back(a, b); } for (const auto &x: kraw) { int a = x.first, b = x.second; int ia = s[a+n].size(), ib = s[b].size(); s[a + n].emplace_back(b, ib, true); s[b].emplace_back(a + n, ia, false); } for (int i = 1; i <= k; i++) { s[i].emplace_back(0, -1, false); } for (int i = 1; i <= n; i++) { int ip = s[i].size(), ik = s[i+n].size(); s[i].emplace_back(i + n, ik, true); s[i + n].emplace_back(i, ip, false); } for (int i = k + 1; i <= n; i++) { int ile = 0; memset(odw + 1, 0, sizeof(bool) * n * 2); for (const auto &x: flip) { s[x.first][x.second].full ^= 1; } flip.clear(); for (int j = i; j <= n; j++) { if (dfs(j + n)) { ile++; for (int x: vodw) odw[x] = false; vodw.clear(); } wynik[ile]++; } } for (int i = 0; i <= k; i++) cout << wynik[i] << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 | #include <iostream> #include <vector> #include <algorithm> #include <set> #include <cstring> #include <cassert> using namespace std; struct sc { int s; int ip; bool full; sc(int a, int b, bool c) : s(a), ip(b), full(c) {} }; int n, m, k; bool odw[200001]; vector<sc> s[200001]; vector<pair<int, int>> kraw, flip; vector<int> vodw; long long wynik[51]; int dfs(int a) { if (odw[a]) return 0; int udalosie = 0, gdzie = 0; odw[a] = 1; vodw.push_back(a); for (int i = 0; i < (int)s[a].size(); i++) { if (s[a][i].full || odw[s[a][i].s]) continue; if (s[a][i].s == 0 || dfs(s[a][i].s)) { udalosie = 1; gdzie = i; break; } } if (udalosie) { int i = gdzie; s[a][i].full = true; flip.emplace_back(a, i); if (s[a][i].ip != -1) { s[s[a][i].s][s[a][i].ip].full = false; flip.emplace_back(s[a][i].s, s[a][i].ip); } } return udalosie; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; kraw.emplace_back(a, b); } for (const auto &x: kraw) { int a = x.first, b = x.second; int ia = s[a+n].size(), ib = s[b].size(); s[a + n].emplace_back(b, ib, true); s[b].emplace_back(a + n, ia, false); } for (int i = 1; i <= k; i++) { s[i].emplace_back(0, -1, false); } for (int i = 1; i <= n; i++) { int ip = s[i].size(), ik = s[i+n].size(); s[i].emplace_back(i + n, ik, true); s[i + n].emplace_back(i, ip, false); } for (int i = k + 1; i <= n; i++) { int ile = 0; memset(odw + 1, 0, sizeof(bool) * n * 2); for (const auto &x: flip) { s[x.first][x.second].full ^= 1; } flip.clear(); for (int j = i; j <= n; j++) { if (dfs(j + n)) { ile++; for (int x: vodw) odw[x] = false; vodw.clear(); } wynik[ile]++; } } for (int i = 0; i <= k; i++) cout << wynik[i] << '\n'; } |