1 条题解
-
0
C++ :
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #include<queue> #define s1 100002 #define s2 200002 #define s3 30005 using namespace std; struct node { int y; int next; }e[s2]; int tot=0; int g[s3]={0}; bool b[s3]={0}; void jian(int x,int y) { e[++tot].y=y; e[tot].next=g[x]; g[x]=tot; } int main() { //freopen("damage.in","r",stdin); //freopen("damage.out","w",stdout); int n,p,c; cin>>p>>c>>n; int x,y,m; queue <int> q; for(int i=1;i<=c;i++) { cin>>x>>y; jian(x,y); jian(y,x); } for(int i=1;i<=n;i++) { cin>>m; q.push(m); b[m]=1; int pos=g[m]; while(pos!=0) { b[e[pos].y]=1; pos=e[pos].next; } } q.push(1); b[1]=1; int sum=1; while(!q.empty()) { int f=q.front(); int pos=g[f]; while(pos!=0) { if(!b[e[pos].y]) { q.push(e[pos].y); b[e[pos].y]=1; sum++; } pos=e[pos].next; } q.pop(); } cout<<p-sum; return 0; }
Pascal :
type ji=^rec; rec=record data:longint; next:ji; end; var a:array[0..30001] of ji; q:array[0..30001] of longint; v:array[0..30001] of boolean; head,tail,n,m,p,i,j,k,ans:longint; pp:ji; procedure insert(x,y:longint); var p:ji; begin new(p); p^.data:=y; p^.next:=a[x]; a[x]:=p; new(p); p^.data:=x; p^.next:=a[y]; a[y]:=p; end; procedure dfs(x:longint); var p:ji; begin v[x]:=true; dec(ans); p:=a[x]; while p<>nil do begin if not v[p^.data] then dfs(p^.data); p:=p^.next; end; end; procedure cannot(x:longint); var p:ji; begin p:=a[x]; v[x]:=true; while p<>nil do begin v[p^.data]:=true; p:=p^.next; end; end; begin readln(n,m,p); for i:=1 to m do begin readln(j,k); if j=k then continue; insert(j,k); end; for i:=1 to p do begin readln(k); cannot(k); end; ans:=n-1; head:=1; tail:=1; q[1]:=1; v[1]:=true; while head<=tail do begin pp:=a[q[head]]; while pp<>nil do begin if not v[pp^.data] then begin v[pp^.data]:=true; dec(ans); inc(tail); q[tail]:=pp^.data; end; pp:=pp^.next; end; inc(head); end; writeln(ans); end.
- 1
信息
- ID
- 659
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者