首页 > 代码库 > More is better

More is better

2024-07-10 03:27:25   218人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1856

真的无语了，一个并查集的水题，竟然做了两个多小时，我都怀疑我自己了，还有智商么？

题意，找出最多认识人的集合

我手残了N次 ，本题1000ms，数组10000000，所以要用哈希查找

#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;int n;int bin[10000001];int ta[10000001];int findx(int x){    int r=x;    while(bin[r]!=r)    {        r=bin[r];    }    int k,j;    k=x;    while(k!=r)    {        j=bin[k];        bin[k]=r;        k=j;    }    return r;}void merge(int x,int y){    int fx=findx(x);    int fy=findx(y);    if(fx!=fy)        bin[fy]=fx;}int main(){    int x,y,max1;    while(scanf("%d",&n)!=EOF)    {        memset(ta,0,sizeof(ta));        for(int i=1;i<=1000000;i++)            bin[i]=i;        //while(n--)//已经多次手惨了，这次贴出来惊醒一下        for(int i=1;i<=n;i++)        {            scanf("%d%d",&x,&y);            merge(x,y);        }        for(int i=1;i<10000001;i++)        {            ta[findx(i)]++;//算法的核心；哈希        }         max1=ta[1];        //刚才把n弄成了0        for(int i=2;i<10000001;i++)        {              if(ta[i]>max1)              max1=ta[i];        }        printf("%d\n",max1);    }    return 0;}
View Code

 


联系
我们