Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <queue>
- int main() {
- int vertex, degree, num, helper;
- std::cin >> vertex;
- std::vector<std::pair<int, int>> able(vertex);
- std::vector<int> used(vertex);
- std::vector<std::vector<int>> graph(vertex);
- std::queue<int> que;
- for (int i = 0; i != vertex; ++i) {
- std::cin >> degree;
- used[i] = degree - 1;
- able[i].second = 1;
- if (degree == 1) {
- que.push(i);
- used[i] = -1;
- }
- for (int j = 0; j != degree; ++j) {
- std::cin >> num;
- graph[i].push_back(num);
- }
- }
- for (int i = 0; i != vertex; ++i) {
- if (graph[i].size() == 1) {
- able[i].first = 0;
- }
- }
- while (!que.empty()) {
- int vert_1 = que.front();
- helper = vert_1;
- que.pop();
- for (int i = 0; i != graph[vert_1].size(); ++i) {
- int vert_2 = graph[vert_1][i];
- if (used[vert_2] > 0) {
- used[vert_2] -= 1;
- able[vert_2].second += able[vert_1].second;
- able[vert_2].first = std::min(able[vert_2].second, able[vert_1].second);
- } else if (used[vert_2] == 0) {
- que.push(vert_2);
- used[vert_2] = -1;
- }
- }
- }
- std::cout << std::min(able[helper].first, able[helper].second) << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement