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
| #include <iostream> #include <string.h> #include <algorithm> using namespace std; const int maxn = 1e5 + 10;
int head[maxn], ver[maxn << 1], next1[maxn << 1]; int dfn[maxn], low[maxn]; int n, m, tot, num, root; bool cut[maxn];
void init() { tot = 0; num = 0; memset(cut,0,sizeof cut); memset(head,0,sizeof head); memset(ver,0,sizeof ver); memset(next1,0,sizeof next1); memset(low,0,sizeof low); memset(dfn,0,sizeof dfn); } void edgeadd(int x,int y) { ver[++tot] = y; next1[tot] = head[x]; head[x] = tot; } void tarjan(int x) { dfn[x] = low[x] = ++num; int out = 0; for (int i = head[x]; i; i = next1[i]) { int to = ver[i]; if (!dfn[to]) { tarjan(to); low[x] = min(low[x],low[to]); if (low[to] >= dfn[x]) { out++; if (x != root || out > 1) { cut[x] = 1; } } } else low[x] = min(low[x],dfn[to]); } } int main() { int n;
while (scanf("%d", &n) && n) { int cur, to; init(); while (scanf("%d", &cur) && cur) { while (getchar() != '\n') { scanf("%d", &to); if (cur == to) continue; edgeadd(cur,to); edgeadd(to,cur); } } for (int i = 1; i <= n; i++) if (!dfn[i]) root = i, tarjan(i); int ans = 0; for (int i = 1; i <= n; i++) if (cut[i]) ans++; printf("%d\n",ans); } return 0; }
|