只要把不能过的周围的点都不能过再dfs一遍就好了。。好像有点贪心的味道
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> using namespace std; struct edgee { int from, to; edgee(int f, int t) :from(f), to(t) {} edgee() {} }; edgee edge[400020]; int edgetot; int first[30010], nextt[400020]; bool isgo[30010]; void addedge(int from, int to) { nextt[edgetot] = first[from]; edge[edgetot] = edgee(from, to); first[from] = edgetot++; nextt[edgetot] = first[to]; edge[edgetot] = edgee(to, from); first[to] = edgetot++; } int P, C, N; int anss = 0; void dfs(int now, int from) { anss++; isgo[now] = 1; for (int i = first[now]; i != -1; i = nextt[i]) { int to = edge[i].to; if (isgo[to] != 1 ) { dfs(to, now); } } } int main() { scanf("%d%d%d", &P, &C, &N); for (int i = 0; i <= P; i++) first[i] = -1; for (int i = 0; i < C; i++) { int a, b; scanf("%d%d", &a, &b); addedge(a, b); } for (int i = 1; i <= N; i++) { int k; scanf("%d", &k); isgo[k] = 1; for (int j = first[k]; j != -1; j = nextt[j]) { int to = edge[j].to; isgo[to] = 1; } } dfs(1, 1); printf("%d\n", P - anss); return 0; }