首页 > 代码库 > ZOJ 3811

ZOJ 3811

2024-07-21 21:13:34   228人阅读

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5343

网络赛这水题没写过太伤了，赛后写了下1A。

当时钻牛角尖一定要用k次bfs，其实一次就够了，把扩展到的节点插入set中，复杂度nlogn

#include <iostream>#include <cstdio>#include <cstring>#include <set>#include <vector>#include <queue>using namespace std ;vector <int> mp[100005] ;set <int> s ;int idx[100005] ;int vis[100005] ;int node[100005] ;int find(int x){    return idx[x]==x?x:idx[x]=find(idx[x]) ;}int n,m,k ;int flag[100005] ;int main(){    int T ;    scanf("%d",&T) ;    while(T--)    {        scanf("%d%d%d",&n,&m,&k) ;        memset(flag,0,sizeof(flag)) ;        for(int i=0 ;i<100005 ;i++)            mp[i].clear() ;        s.clear() ;        memset(vis,0,sizeof(vis)) ;        for(int i=1 ;i<=n ;i++)            idx[i]=i ;        for(int i=0 ;i<k ;i++)        {            int x ;            scanf("%d",&x) ;            flag[x]=1 ;        }        int ff=1 ;        while(m--)        {            int a,b ;            scanf("%d%d",&a,&b) ;            mp[a].push_back(b) ;            mp[b].push_back(a) ;            int p=find(a) ;            int q=find(b) ;            if(p!=q)                idx[p]=q ;        }        for(int i=2 ;i<=n ;i++)        {            if(find(idx[1])!=find(idx[i]))            {                ff=0 ;                break ;            }        }        int L ;        scanf("%d",&L) ;        if(L!=k)ff=0 ;        for(int i=0 ;i<L ;i++)            scanf("%d",&node[i]) ;        queue <int> q ;        s.insert(node[0]) ;        for(int j=0 ;j<L ;j++)        {            if(s.find(node[j])!=s.end())            {                q.push(node[j]) ;                vis[node[j]]=1 ;                while(!q.empty())                {                    int u=q.front() ;                    q.pop() ;                    for(int i=0 ;i<mp[u].size() ;i++)                    {                        if(!vis[mp[u][i]])                        {                            vis[mp[u][i]]=1 ;                            if(flag[mp[u][i]])                            {                                s.insert(mp[u][i]) ;                            }                            else                            {                                q.push(mp[u][i]) ;                            }                        }                    }                }                continue ;            }            else            {                ff=0 ;                break ;            }        }        if(ff)puts("Yes") ;        else puts("No") ;    }    return 0 ;}
View Code

 

 

ZOJ 3811


联系
我们