Advertisement
Guest User

Untitled

a guest
Sep 30th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LL long long
  4. #define endl '\n'
  5. #define all(x) x.begin(), x.end()
  6. #define fill(a, b) memset(a, b, sizeof a)
  7.  
  8. const double eps = 1e-15;
  9. const double pi = acos(-1.0);
  10. const LL Mod = 1000000007;
  11. const int N = 1e3 + 5;
  12. int ks = 0;
  13.  
  14.  
  15.  
  16. vector <int> g[N];
  17. bool used[N], AP[N];
  18. int low[N], in[N], timer;
  19.  
  20. void dfs(int cur, int par = -1) {
  21. int son = 0;
  22. used[cur] = true;
  23. low[cur] = in[cur] = ++timer;
  24. for (auto to : g[cur]) {
  25. if (to == par) continue;
  26. if (used[to]) {
  27. low[cur] = min(low[cur], in[to]);
  28. } else {
  29. dfs(to, cur);
  30. low[cur] = min(low[cur], low[to]);
  31. son++;
  32. if (low[to] >= in[cur] && par != -1) AP[cur] = true;
  33. }
  34. }
  35. if (par == -1 && son > 1) AP[cur] = true;
  36. }
  37.  
  38. int main() {
  39. ios::sync_with_stdio(0), cin.tie(0);
  40. int n;
  41. while (cin >> n && n) {
  42. for (int i = 1; i < N; i++) {
  43. g[i].clear();
  44. used[i] = AP[i] = false;
  45. }
  46. timer = 0;
  47. cin.ignore();
  48. while (true) {
  49. string s;
  50. getline(cin, s);
  51. istringstream iss(s);
  52. int x, y;
  53. iss >> x;
  54. if (x == 0) break;
  55. while (iss >> y) {
  56. g[x].emplace_back(y);
  57. g[y].emplace_back(x);
  58. }
  59. }
  60. for (int i = 1; i <= n; i++) {
  61. if (!used[i]) {
  62. dfs(i);
  63. }
  64. }
  65. int ans = 0;
  66. for (int i = 1; i <= n; i++) {
  67. if (AP[i] == true) {
  68. ans++;
  69. }
  70. }
  71. cout << ans << endl;
  72. }
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement