Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- using namespace std;
- using i64 = long long;
- const int MAXN = 1e5+5;
- const int INF = 0x3f3f3f3f;
- vector<int> gr[MAXN], gr2[MAXN];
- int used[MAXN], tin[MAXN], low[MAXN];
- int n, m, b, timer;
- int isBase[MAXN], isCutpoint[MAXN];
- int bases[MAXN], hasBases[MAXN];
- int cnt[MAXN];
- void is_cutpoint(int u) {
- //cout << u+1 << '\n';
- isCutpoint[u] = true;
- return;
- }
- vector<int> ans;
- void dfs(int u, int p = -1) {
- bases[u] = isBase[u];
- hasBases[u] = 0;
- used[u] = true;
- tin[u] = low[u] = timer++;
- int children = 0;
- for (int to : gr[u]) if (to != p) {
- if (used[to]) { //Is a back edge
- low[u] = min(low[u], tin[to]);
- ++hasBases[to];
- // if (to == 0) {
- // cout << u+1 << ' ' << to+1 << '\n';
- // }
- // ++hasBases[u];
- // if (u == 0) {
- // cout << u+1 << ' ' << to+1 << '\n';
- // }
- } else {
- gr2[u].push_back(to);
- gr2[to].push_back(u);
- dfs(to, u);
- bases[u] += bases[to];
- hasBases[u] += (hasBases[to] or bases[to] > 0);
- low[u] = min(low[u], low[to]);
- if (low[to] >= tin[u] and p != -1) {
- is_cutpoint(u);
- }
- ++children;
- }
- }
- if (p == -1 and children > 1) {
- is_cutpoint(u);
- }
- }
- void solve(int u, int p, int root) {
- used[u] = true;
- for (int to : gr2[u]) if (to != p and !used[to]) {
- // cout << u+1 << " -> " << to+1 << '\n';
- if (isCutpoint[to]) {
- int basesRoot = bases[root] - bases[to];
- if (hasBases[to] + (basesRoot > 0 or (low[u] >= low[to])) < gr[to].size() and !isBase[to]) {
- // cout << u+ 1<< ' ' << to+1 << ' ' << hasBases[to] << ' ' << bases[to] << ' ' << basesRoot << ' ' << bases[root] << '\n';
- ans.push_back(to);
- }
- } else {
- if (hasBases[to] + (bases[root] > 0) < gr[to].size() and !isBase[to]) {
- // cout << u+ 1<< ' ' << to+1 << ' ' << hasBases[to] << ' ' << bases[to] << ' ' << bases[root] << '\n';
- ans.push_back(to);
- }
- }
- solve(to, u, root);
- }
- if (u == root and !isBase[root]) {
- // cout << u+1 << ' ' << hasBases[root] << '\n';
- if (hasBases[root] < gr[root].size()) {
- ans.push_back(root);
- }
- }
- }
- void find_cutpoints() {
- timer = 0;
- for (int i = 0; i < n; ++i) {
- used[i] = false;
- tin[i] = -1;
- low[i] = -1;
- }
- for (int i = 0; i < n; ++i)
- if (!used[i]) dfs(i);
- }
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- cin >> n >> m >> b;
- for (int i = 0; i < m; ++i) {
- int u, v; cin >> u >> v, --u, --v;
- gr[u].push_back(v);
- gr[v].push_back(u);
- }
- for (int i = 0; i < b; ++i) {
- int x; cin >> x, --x;
- isBase[x] = true;
- }
- find_cutpoints();
- for (int i = 0; i < n; ++i) {
- used[i] = false;
- //cout << bases[i] << ' ';
- } //cout << '\n';
- solve(0, -1, 0);
- sort(ans.begin(), ans.end());
- ans.erase(unique(ans.begin(), ans.end()), ans.end());
- cout << ans.size() << '\n';
- for (int i = 0; i < (int)ans.size(); ++i) {
- cout << ans[i]+1 << " \n"[i==(int)ans.size()-1];
- }
- }
- /*
- 5 4 1
- 1 2
- 2 3
- 3 4
- 4 5
- 1
- 5 4 1
- 1 2
- 2 3
- 3 4
- 4 5
- 5
- 7 8 3
- 1 2
- 1 3
- 1 4
- 2 5
- 2 6
- 5 6
- 3 4
- 3 7
- 4 5 6
- 7 8 3
- 3 2
- 3 1
- 3 4
- 2 5
- 2 6
- 5 6
- 1 4
- 1 7
- 4 5 6
- 9 8 2
- 1 2
- 2 3
- 3 4
- 4 7
- 3 6
- 3 5
- 5 8
- 6 9
- 8 9
- 9 8 2
- 1 2
- 2 3
- 3 4
- 4 7
- 3 6
- 3 5
- 5 8
- 6 9
- 9 7
- */
Advertisement