2 条题解

  • 3
    @ 2024-3-12 21:00:07

    bfs 即可,总结来说是道图 + bfs。

    首先读入关系 uuvv 相连,如果用 au,v=1a_{u,v}=1 表示 uuvv 连通,那么 au,v=av,u=1a_{u,v} = a_{v,u}=1

    然后对于每个结点(1n1\sim n) bfs,如果说 visi=0vis_i = 0(没有访问过),那么对结点 ii bfs 其所有连通(直接或者间接连通)的点,遍历完后对于答案 11 的贡献为 11

    那么对于答案 22,直接一边 bfs,一边累加家庭人员,每次 bfs 后比较最大值即可。

    #include <bits/stdc++.h>
    using namespace std;
    
    #define int long long
    #define rep(i,x,y) for(int i=x;i<=y;i++)
    #define rrep(i,x,y) for(int i=x;i>=y;i--)
    #define sc scanf
    #define pr printf
    #define max(a,b) a>b?a:b
    #define endline pr("\n")
    inline int read(){int s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-') w=-1;c=getchar();}while(isdigit(c)){s=(s<<1)+(s<<3)+(c^48);c=getchar();}return s*w;}
    
    const int N=105;
    int n,k,tot,ans;
    bool vis[N];
    vector <int> a[N];
    queue <int> q;
    
    inline void bfs(int i){
      q.push(i);
      vis[i]=1;
      int family=1;//初始化,一开始结点 i 独自一个家庭。
      while(!q.empty()){
        int now=q.front();
        q.pop();
        int len=a[now].size();
        rep(j,0,len-1)
          if(!vis[a[now][j]]){//没有访问过。
            ++family;//累加家庭人员数量。
            vis[a[now][j]]=1;
            q.push(a[now][j]);//入队。
          }
      }
      ans=max(ans,family);
    }
    
    signed main(){
      n=read();k=read();
      rep(i,1,k){
        int u=read(),v=read();
        a[u].push_back(v);
        a[v].push_back(u);
      }
      rep(i,1,n)
        if(!vis[i]){
          ++tot;
          bfs(i);
        }
      pr("%lld %lld\n",tot,ans);
      return 0;
    }
    
    • 1
      @ 2024-3-12 21:04:18

      这题还可以用并查集解。

      对于每个关系,直接合并。

      然后查找每个结点的父亲(间接也算,即为 find(i)\operatorname{find}(i)),累加 find(i)find(i) 的个数,用于统计最大值。

      如果说 find(i)=i\operatorname{find}(i) = i,说明没有其祖先为自己,并对答案 11 的贡献为 11

      没有代码()

      • 1

      信息

      ID
      72
      时间
      1000ms
      内存
      256MiB
      难度
      2
      标签
      (无)
      递交数
      72
      已通过
      46
      上传者