1 条题解

  • 0
    @ 2025-2-14 21:09:17

    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
    上传者