[uva] 315 – network

#include <iostream>
#include <sstream>
#include <vector>
#ifdef LOCAL
#include "stloutput.h"
#endif
#define INF 1000000000

using namespace std;

void (int x, vector<vector<int>> &g, vector<int> &dfs_lo,
         vector<int> &dfs_num, vector<int> &dfs_par, int &cnt,
         vector<bool> &ans, int &root_kids, int &root) {
    dfs_lo[x] = dfs_num[x] = cnt++;
    for (auto i : g[x]) {
        if (dfs_num[i] == -1) {
            if (x == root) root_kids++;
            dfs_par[i] = x;
            dfs(i, g, dfs_lo, dfs_num, dfs_par, cnt, ans, root_kids, root);
            if (dfs_lo[i] >= dfs_num[x]) {
                ans[x] = 1;
            }
            dfs_lo[x] = min(dfs_lo[i], dfs_lo[x]);
        } else if (dfs_par[x] != i) {
            dfs_lo[x] = min(dfs_lo[x], dfs_num[i]);
        }
    }
}

int main() {
    int n;
    while (cin >> n, n) {
        vector<vector<int>> g(n);
        int m;
        while (cin >> m, m) {
            m--;
            string s;
            getline(cin, s);
            stringstream ss(s);
            int tmp;
            while (ss >> tmp) g[m].push_back(tmp - 1), g[tmp - 1].push_back(m);
        }
        vector<int> dfs_lo(n), dfs_num(n, -1), dfs_par(n, -1);
        vector<bool> ans(n);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (dfs_num[i] == -1) {
                int root_kids = 0;
                dfs(i, g, dfs_lo, dfs_num, dfs_par, cnt, ans, root_kids, i);
                ans[i] = (root_kids > 1);
            }
        }
        
        cout << count(ans.begin(), ans.end(), 1) << endl;
    }
}