Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define LL long long
- #define endl '\n'
- #define all(x) x.begin(), x.end()
- #define fill(a, b) memset(a, b, sizeof a)
- const double eps = 1e-15;
- const double pi = acos(-1.0);
- const LL Mod = 1000000007;
- const int N = 1e3 + 5;
- int ks = 0;
- vector <int> g[N];
- bool used[N], AP[N];
- int low[N], in[N], timer;
- void dfs(int cur, int par = -1) {
- int son = 0;
- used[cur] = true;
- low[cur] = in[cur] = ++timer;
- for (auto to : g[cur]) {
- if (to == par) continue;
- if (used[to]) {
- low[cur] = min(low[cur], in[to]);
- } else {
- dfs(to, cur);
- low[cur] = min(low[cur], low[to]);
- son++;
- if (low[to] >= in[cur] && par != -1) AP[cur] = true;
- }
- }
- if (par == -1 && son > 1) AP[cur] = true;
- }
- int main() {
- ios::sync_with_stdio(0), cin.tie(0);
- int n;
- while (cin >> n && n) {
- for (int i = 1; i < N; i++) {
- g[i].clear();
- used[i] = AP[i] = false;
- }
- timer = 0;
- cin.ignore();
- while (true) {
- string s;
- getline(cin, s);
- istringstream iss(s);
- int x, y;
- iss >> x;
- if (x == 0) break;
- while (iss >> y) {
- g[x].emplace_back(y);
- g[y].emplace_back(x);
- }
- }
- for (int i = 1; i <= n; i++) {
- if (!used[i]) {
- dfs(i);
- }
- }
- int ans = 0;
- for (int i = 1; i <= n; i++) {
- if (AP[i] == true) {
- ans++;
- }
- }
- cout << ans << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement