切换到宽版
发帖 回复
返回列表
  • 12290阅读
  • 1回复

RQNOJ480 [复制链接]

 上一主题 下一主题
离线cpp_student
OIFans入门选手
 
只看楼主 倒序阅读 0 发表于: 2009-07-31
并查集

复制代码
  1. /*
  2. 查看题目 Show Problem
  3. 题目:相连的农场
  5. 问题编号:480 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
  7. My Flag:Unsubmited
  9. 题目类型
  10. 图结构  
  12. 描述
  13. Farmer John的农场被一次意外事故破坏了，有一些农场与其他的农场之间有道路相连，而有些道路却已被破坏。这使得Farmer John 无法了解到从一个农场能否到达另一个农场。你的任务就是帮助Farmer John来了解哪些农场是连通的。
  14. 给出一个无权图，请你按顺序输出图中所有的连通块。
  15. 输入格式
  16. 第一行是点数n(1<=n<=500)，以下n行为这个图的邻接矩阵。
  17. 输出格式
  18. 第一行是连通块的个数m，以下m行，每一行是一个连通块中农场的序号，末尾有一空格。
  19. 注意，输出时，每个连通块中的点按点序号的大小顺序输出，而个个连通块按连通块中的第一个点的顺序输出。
  20. 样例输入
  21. 5
  22. 0 1 0 1 0
  23. 1 0 0 0 0
  24. 0 0 0 0 1
  25. 1 0 0 0 0
  26. 0 0 1 0 0
  27.   
  28. 样例输出
  29. 2
  30. 1 2 4
  31. 3 5  
  35. */
  36. #include<iostream>
  37. using namespace std;
  38. int father[501],n,m;
  39. int road[501][501];
  40. struct block
  41. {
  42.     int num,father;
  43.     int ns[501];
  44. } bs[501];
  45. void initialize(){
  46.     scanf("%d",&n);
  47.     for (int i=1;i<=n;++i)
  48.         father[i]=i;
  49.     for (int i=1;i<=n;++i)
  50.         for (int j=1;j<=n;++j)
  51.             scanf("%d",&road[i][j]);
  52. }
  53. int getfather(int v){
  54.     if (father[v]==v) return v;
  55.     return father[v]=getfather(father[v]);
  56. }
  57. void join(int v1,int v2){
  58.     int f1,f2;
  59.     f1=getfather(v1);
  60.     f2=getfather(v2);
  61.     if (f1!=f2) father[f1]=f2;
  62. }
  63. int cmp(const void *a,const void *b){
  64.     return *(int *)a-*(int *)b;
  65. }
  66. int cmp1(const void *a,const void *b){
  67.     return (*(block *)a).ns[0]-(*(block *)b).ns[0];
  68. }
  69. void measure(){
  70.     for (int i=1;i<=n;++i)
  71.         for (int j=1;j<=n;++j)
  72.             if (road[i][j]==1) join(i,j);
  73.     m=0;
  74.     for (int i=1;i<=n;++i)
  75.         if (father[i]==i){
  76.            bs[m].num=0;
  77.            bs[m].father=i;
  78.            ++m;
  79.         }
  80.     for (int i=1;i<=n;++i)
  81.         for (int j=0;j<m;++j)
  82.             if (bs[j].father==getfather(i))
  83.                bs[j].ns[bs[j].num++]=i;
  84.     for (int j=0;j<m;++j)
  85.         qsort(bs[j].ns,bs[j].num,sizeof(bs[j].ns[0]),cmp);
  86.     qsort(bs,m,sizeof(bs[0]),cmp1);
  87. }
  88. void output(){
  89.     int j;
  90.     cout<<m;
  91.     for (j=0;j<m-1;++j){
  92.         cout<<endl;
  93.         for (int k=0;k<bs[j].num;++k)
  94.             cout<<bs[j].ns[k]<<' ';
  95.     }
  96.     cout<<endl;
  97.     for (int k=0;k<bs[j].num;++k){
  98.         if (k!=0) cout<<' ';
  99.         cout<<bs[j].ns[k];
  100.     }
  101. }
  102. int main (void){
  103.     initialize();
  104.     measure();
  105.     output();
  106. //    while (1);
  107.     return 0;
  108. }
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
离线魔哒蒂斯
OIFans复赛选手
只看该作者 1 发表于: 2009-09-12
？？？
回复
举报
发帖 回复
返回列表
快速回复
限100 字节
 
上一个 下一个