切换到宽版
  • 7734阅读
  • 1回复

RQNOJ480 [复制链接]

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

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