Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <climits>
- #include <queue>
- #include <set>
- using namespace std;
- struct vertex {
- set<int> connected;
- int edges;
- };
- void fillTrees(vector<vertex> &trees, int v) {
- for (int i = 0; i != v; ++i) {
- int d;
- cin >> d;
- trees[i].edges = d;
- for (int j = 0; j != d; ++j) {
- int vert;
- cin >> vert;
- trees[i].connected.insert(vert);
- }
- }
- }
- void findAns(vector<vertex> &trees) {
- queue<int> checkList;
- int counter = 0;
- for (int i = 0; i != trees.size(); ++i)
- checkList.push(i);
- while (!checkList.empty()) {
- int i = checkList.front();
- checkList.pop();
- if(trees[i].edges == 1) {
- int point = *trees[i].connected.begin();
- for (auto it = trees[point].connected.begin(); it != trees[point].connected.end(); ++it) {
- if (trees[*it].edges != 0) {
- trees[*it].connected.erase(point);
- trees[*it].edges--;
- }
- }
- trees[point].edges = 0;
- counter++;
- } else if (trees[i].edges > 1){
- checkList.push(i);
- }
- }
- cout << counter;
- }
- int main() {
- int v;
- cin >> v;
- vector<vertex> trees(v);
- fillTrees(trees, v);
- findAns(trees);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement