UOJ Logo insilent的博客

博客

#76. 家庭问题

2018-02-23 12:05:31 By insilent

这是bfs的做法

我认为本题应是并查集


#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int ans;
int n,k;
int u_max;
int board[105],zhi[105];  //zhi是记录家庭人数的  board是记录所属家庭的 
bool road[105][105];      //记录节点之间的关系 
int num;
void bfs(int place)
{
    ans++;                  //此时ans是家族编号 
    board[place]=ans;
    queue <int> q;          //经典队列做法 
    q.push(place);
    num=0;
    while(!q.empty())
    {
        num+=1;
        int tmp=q.front();
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if((!board[i]) && road[tmp][i])
            {
                board[i]=ans;
                q.push(i);
            }
        }    
    } 
    zhi[ans]=num;        //记录此家族人数 
}
int main()
{
    scanf("%d%d",&n,&k);
    int op1,op2;
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&op1,&op2);
        road[op1][op2]=road[op2][op1]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(!board[i])
        {
            bfs(i);
            u_max=max(u_max,zhi[board[i]]);
        } 
    }
    printf("%d %d",ans,u_max);
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。