danielvitor23

Plano B

Aug 9th, 2023 (edited)
1,593
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. using i64 = long long;
  6. const int MAXN = 1e5+5;
  7. const int INF = 0x3f3f3f3f;
  8.  
  9. vector<int> gr[MAXN], gr2[MAXN];
  10. int used[MAXN], tin[MAXN], low[MAXN];
  11. int n, m, b, timer;
  12.  
  13. int isBase[MAXN], isCutpoint[MAXN];
  14. int bases[MAXN], hasBases[MAXN];
  15. int cnt[MAXN];
  16.  
  17. void is_cutpoint(int u) {
  18.   //cout << u+1 << '\n';
  19.   isCutpoint[u] = true;
  20.     return;
  21. }
  22.  
  23. vector<int> ans;
  24.  
  25. void dfs(int u, int p = -1) {
  26.   bases[u] = isBase[u];
  27.   hasBases[u] = 0;
  28.     used[u] = true;
  29.     tin[u] = low[u] = timer++;
  30.     int children = 0;
  31.  
  32.     for (int to : gr[u]) if (to != p) {
  33.         if (used[to]) { //Is a back edge
  34.             low[u] = min(low[u], tin[to]);
  35.       ++hasBases[to];
  36.       // if (to == 0) {
  37.       //   cout << u+1 << ' ' << to+1 << '\n';
  38.       // }
  39.       // ++hasBases[u];
  40.       // if (u == 0) {
  41.         // cout << u+1 << ' ' << to+1 << '\n';
  42.       // }
  43.         } else {
  44.       gr2[u].push_back(to);
  45.       gr2[to].push_back(u);
  46.             dfs(to, u);
  47.       bases[u] += bases[to];
  48.       hasBases[u] += (hasBases[to] or bases[to] > 0);
  49.             low[u] = min(low[u], low[to]);
  50.             if (low[to] >= tin[u] and p != -1) {
  51.                 is_cutpoint(u);
  52.             }
  53.             ++children;
  54.         }
  55.     }
  56.  
  57.     if (p == -1 and children > 1) {
  58.         is_cutpoint(u);
  59.   }
  60. }
  61.  
  62. void solve(int u, int p, int root) {
  63.     used[u] = true;
  64.  
  65.     for (int to : gr2[u]) if (to != p and !used[to]) {
  66.     // cout << u+1 << " -> " << to+1 << '\n';
  67.         if (isCutpoint[to]) {
  68.       int basesRoot = bases[root] - bases[to];
  69.       if (hasBases[to] + (basesRoot > 0 or (low[u] >= low[to])) < gr[to].size() and !isBase[to]) {
  70.         // cout << u+ 1<< ' ' << to+1 << ' ' << hasBases[to] << ' ' << bases[to] << ' ' << basesRoot << ' ' << bases[root] << '\n';
  71.         ans.push_back(to);
  72.       }
  73.     } else {
  74.       if (hasBases[to] + (bases[root] > 0) < gr[to].size() and !isBase[to]) {
  75.         // cout << u+ 1<< ' ' << to+1 << ' ' << hasBases[to] << ' ' << bases[to] << ' ' << bases[root] << '\n';
  76.         ans.push_back(to);
  77.       }
  78.     }
  79.  
  80.     solve(to, u, root);
  81.   }
  82.  
  83.     if (u == root and !isBase[root]) {
  84.       // cout << u+1 << ' ' << hasBases[root] << '\n';
  85.     if (hasBases[root] < gr[root].size()) {
  86.       ans.push_back(root);
  87.     }
  88.   }
  89. }
  90.  
  91. void find_cutpoints() {
  92.     timer = 0;
  93.     for (int i = 0; i < n; ++i) {
  94.         used[i] = false;
  95.         tin[i] = -1;
  96.         low[i] = -1;
  97.     }
  98.     for (int i = 0; i < n; ++i)
  99.         if (!used[i]) dfs(i);
  100. }
  101.  
  102. int main() {
  103.   cin.tie(0)->sync_with_stdio(0);
  104.  
  105.   cin >> n >> m >> b;
  106.  
  107.   for (int i = 0; i < m; ++i) {
  108.     int u, v; cin >> u >> v, --u, --v;
  109.     gr[u].push_back(v);
  110.     gr[v].push_back(u);
  111.   }
  112.  
  113.   for (int i = 0; i < b; ++i) {
  114.     int x; cin >> x, --x;
  115.     isBase[x] = true;
  116.   }
  117.  
  118.   find_cutpoints();
  119.  
  120.     for (int i = 0; i < n; ++i) {
  121.         used[i] = false;
  122.     //cout << bases[i] << ' ';
  123.   } //cout << '\n';
  124.  
  125.   solve(0, -1, 0);
  126.  
  127.   sort(ans.begin(), ans.end());
  128.   ans.erase(unique(ans.begin(), ans.end()), ans.end());
  129.  
  130.   cout << ans.size() << '\n';
  131.   for (int i = 0; i < (int)ans.size(); ++i) {
  132.     cout << ans[i]+1 << " \n"[i==(int)ans.size()-1];
  133.   }
  134. }
  135. /*
  136. 5 4 1
  137. 1 2
  138. 2 3
  139. 3 4
  140. 4 5
  141. 1
  142.  
  143. 5 4 1
  144. 1 2
  145. 2 3
  146. 3 4
  147. 4 5
  148. 5
  149.  
  150. 7 8 3
  151. 1 2
  152. 1 3
  153. 1 4
  154. 2 5
  155. 2 6
  156. 5 6
  157. 3 4
  158. 3 7
  159. 4 5 6
  160.  
  161. 7 8 3
  162. 3 2
  163. 3 1
  164. 3 4
  165. 2 5
  166. 2 6
  167. 5 6
  168. 1 4
  169. 1 7
  170. 4 5 6
  171.  
  172. 9 8 2
  173. 1 2
  174. 2 3
  175. 3 4
  176. 4 7
  177. 3 6
  178. 3 5
  179. 5 8
  180. 6 9
  181. 8 9
  182.  
  183. 9 8 2
  184. 1 2
  185. 2 3
  186. 3 4
  187. 4 7
  188. 3 6
  189. 3 5
  190. 5 8
  191. 6 9
  192. 9 7
  193. */
Advertisement
Comments
Add Comment
Please, Sign In to add comment