[关闭]
@Chilling 2017-02-16T17:55:05.000000Z 字数 2468 阅读 1127

HDU-1285: 确定比赛名次(邻接矩阵 | 邻接表)

拓扑排序


Description

有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组,每组中的第一行为二个数N,M;其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。

其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3
1 2
2 3
4 3

Sample Output

1 2 4 3

拓扑排序: 都是模板

  • 从有向图中选取一个没有前驱(即入度为0)的顶点,并输出之;
  • 从有向图中删去此顶点以及所有以它为尾的弧;
    重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。

邻接矩阵

用二维数组实现,如果数据太多就不行了。

  1. void topsort()
  2. {
  3. int i,j,k=0,c;
  4. for(i=1;i<n+1;i++) //遍历n次
  5. {
  6. for(j=1;j<n+1;j++) //找出入度为0的节点
  7. {
  8. if(in[j]==0) //如果入度为0了
  9. {
  10. in[j]--; //减为-1,下次就不会再找它
  11. ans[k++]=j; //将找到的节点存入数组,其实也可以直接输出
  12. for(c=1;c<n+1;c++) //删除与该节点关联的边
  13. {
  14. if(ma[j][c]==1)
  15. in[c]--;
  16. }
  17. break;
  18. }
  19. }
  20. }
  21. }
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<string.h>
  4. int ma[505][505],in[505],ans[505],n,m;
  5. void topsort()
  6. {
  7. int i,j,k=0,c;
  8. for(i=1;i<n+1;i++) //遍历n次
  9. {
  10. for(j=1;j<n+1;j++) //找出入度为0的节点
  11. {
  12. if(in[j]==0)
  13. {
  14. in[j]--;
  15. ans[k++]=j;
  16. for(c=1;c<n+1;c++) //删除与该节点关联的边
  17. {
  18. if(ma[j][c]==1)
  19. in[c]--;
  20. }
  21. break;
  22. }
  23. }
  24. }
  25. }
  26. int main()
  27. {
  28. int i,x,y;
  29. while(scanf("%d%d",&n,&m)!=EOF)
  30. {
  31. memset(ma,0,sizeof(ma));
  32. memset(in,0,sizeof(in));
  33. memset(ans,0,sizeof(ans));
  34. for(i=0;i<m;i++)
  35. {
  36. scanf("%d%d",&x,&y);
  37. if(ma[x][y]==0) //判重边,这里很重要
  38. {
  39. ma[x][y]=1;
  40. in[y]++; //入度
  41. }
  42. }
  43. topsort();
  44. printf("%d",ans[0]);
  45. for(i=1;i<n;i++)
  46. printf(" %d",ans[i]);
  47. printf("\n");
  48. }
  49. return 0;
  50. }

邻接表

节约内存,数据多的时候使用。抄的模板,有好多地方不知道是怎么回事,但是会用就好

  1. struct cmp
  2. {
  3. bool operator()(const int &a,const int &b)const
  4. {
  5. return a>b;
  6. }
  7. };
  1. void topsort()
  2. {
  3. priority_queue<int,vector<int>,cmp>q;
  4. int s=0;
  5. for(int i=1;i<=n;i++)
  6. {
  7. if(in[i]==0)
  8. q.push(i);
  9. }
  10. while(!q.empty())
  11. {
  12. int now=q.top(); //弹出的是入度为0的并且更小的那个数字
  13. q.pop();
  14. a[s++]=now; //存入数组
  15. int l=v[now].size();
  16. for(int i=0;i<l;i++)
  17. {
  18. int k=v[now][i];
  19. in[k]--;
  20. if(in[k]==0)
  21. q.push(k);
  22. }
  23. }
  24. }
  1. #include<stdio.h>
  2. #include<vector>
  3. #include<queue>
  4. #include<string.h>
  5. using namespace std;
  6. vector<int>v[505];
  7. int in[505],a[505];
  8. int n,m;
  9. struct cmp
  10. {
  11. bool operator()(const int &a,const int &b)const
  12. {
  13. return a>b;
  14. }
  15. };
  16. void topsort()
  17. {
  18. priority_queue<int,vector<int>,cmp>q;
  19. int s=0;
  20. for(int i=1;i<=n;i++)
  21. {
  22. if(in[i]==0)
  23. q.push(i);
  24. }
  25. while(!q.empty())
  26. {
  27. int now=q.top();
  28. q.pop();
  29. a[s++]=now;
  30. int l=v[now].size();
  31. for(int i=0;i<l;i++)
  32. {
  33. int k=v[now][i];
  34. in[k]--;
  35. if(in[k]==0)
  36. q.push(k);
  37. }
  38. }
  39. printf("%d",a[0]);
  40. for(int i=1;i<n;i++)
  41. printf(" %d",a[i]);
  42. printf("\n");
  43. }
  44. int main()
  45. {
  46. int i,x,y,sum;
  47. while(scanf("%d%d",&n,&m)!=EOF)
  48. {
  49. memset(in,0,sizeof(in));
  50. memset(a,0,sizeof(a));
  51. for(i=0;i<m;i++)
  52. {
  53. scanf("%d%d",&x,&y);
  54. v[x].push_back(y);
  55. in[y]++;
  56. }
  57. topsort();
  58. for(i=1;i<=n;i++)
  59. v[i].clear();
  60. }
  61. return 0;
  62. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注