bzoj1574[Usaco2009 Jan]地震损坏Damage*

bzoj1574[Usaco2009 Jan]地震损坏Damage

题意：

n点m边无向图，知道p条信息ai，表示ai没被损坏但它和点1不联通（损坏的点不能通行），问有多少点和1联通（不包括损坏的点）。n≤30000，m≤100000。

题解：

有一个结论，最优删点方案应该是对每个信息ai，将所有ai的相邻点均设为损坏。在这之后DFS求联通性即可。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 30010
using namespace std;

inline int read(){
    char ch=getchar(); int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
struct e{int t,n;}es[maxn*8]; int g[maxn],ess;
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;}
bool vis[maxn]; int n,m,p,ans;
void dfs(int x){
    ans++; for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t])vis[es[i].t]=1,dfs(es[i].t);
}
int main(){
    n=read(); m=read(); p=read(); inc(i,1,m){int x=read(),y=read(); pe(x,y); pe(y,x);}
    inc(i,1,p){int x=read(); for(int j=g[x];j;j=es[j].n)if(es[j].t!=x)vis[es[j].t]=1;}
    vis[1]=1; dfs(1); printf("%d",n-ans); return 0;
}

20160926