• 标程的改造版本,Nankai卡的好紧哟,好容易过了!一边写一边看标程,跑得好快的标程被我一写,又慢了!~~~~吐血中!
  1. #include <iostream>
  2. #include <vector>
  3. #define N 10005
  4. using namespace std;
  5.  
  6. struct VexNode
  7. {
  8. int ancestor,deep,total,pre;
  9. bool visited;
  10. };
  11. struct ArcNode
  12. {
  13. int v;
  14. ArcNode(int _v):v(_v){};
  15. };
  16. typedef vector<ArcNode> Graph;
  17. int vexNum;
  18. Graph g[N];
  19. VexNode vex[N];
  20. vector<int> g1[N];
  21.  
  22. void CreatGraph()
  23. {
  24. memset(g,0,sizeof(g));
  25. int m,v1,v2;
  26. scanf("%d%d",&vexNum,&m);
  27. for(int i=0;i<vexNum+m;i++)
  28. {
  29. scanf("%d%d",&v1,&v2);
  30. g[v1].push_back(ArcNode(v2));
  31. g[v2].push_back(ArcNode(v1));
  32. }
  33. }
  34. void Dfs(int u,int father,int time)
  35. {
  36.  
  37. vex[u].visited=true;
  38. vex[u].deep=time;
  39. vex[u].ancestor=time;
  40. Graph::iterator pg;
  41. for(pg=g[u].begin();pg!=g[u].end();pg++)
  42. {
  43. if(vex[pg->v].visited==true&&pg->v!=father)
  44. vex[u].ancestor=min(vex[u].ancestor,vex[pg->v].deep);
  45. else if(vex[pg->v].visited==false)
  46. {
  47. Dfs(pg->v,u,time+1);
  48. vex[pg->v].pre=u;
  49. vex[u].total++;
  50. vex[u].ancestor=min(vex[u].ancestor,vex[pg->v].ancestor);
  51. }
  52. }
  53. }
  54. void Solve()
  55. {
  56. memset(vex,0,sizeof(vex));
  57. memset(g1,0,sizeof(g1));
  58. vex[1].pre=0;
  59. Dfs(1,0,0);
  60. Graph::iterator pg,pg1;
  61. for(int i=1;i<=vexNum;i++)
  62. for(pg=g[i].begin();pg!=g[i].end();pg++)//find i’s all ancestor
  63. {
  64. if(vex[pg->v].pre==i)
  65. {
  66. if(vex[pg->v].total==0)
  67. {
  68. g1[i].push_back(pg->v);
  69. g1[pg->v].push_back(i);
  70. int aMin=INT_MAX,temp;
  71. for(pg1=g[pg->v].begin();pg1!=g[pg->v].end();pg1++){
  72. if(vex[pg1->v].deep<aMin)
  73. {
  74. aMin=vex[pg1->v].deep;
  75. temp=pg1->v;
  76. }
  77. }
  78. g1[pg->v].push_back(temp);//here!
  79. g1[temp].push_back(pg->v);
  80. }
  81. else if(vex[pg->v].total==1)
  82. {
  83. if(i==1)
  84. {
  85. g1[i].push_back(pg->v);
  86. g1[pg->v].push_back(i);
  87. }
  88. else
  89. {
  90. int w;
  91. for(pg1=g[pg->v].begin();pg1!=g[pg->v].end();pg1++){
  92. if(vex[pg1->v].pre==pg->v)
  93. {
  94. w=pg1->v;//find it’s child
  95. break;
  96. }
  97. }
  98. if(vex[w].ancestor<vex[i].deep)
  99. {
  100. g1[i].push_back(pg->v);
  101. g1[pg->v].push_back(i);
  102. }
  103. else
  104. {//w
  105. int x,aMin=INT_MAX;
  106. for(pg1=g[pg->v].begin();pg1!=g[pg->v].end();pg1++)
  107. {
  108. if(vex[pg1->v].deep<aMin)
  109. {
  110. x=pg1->v;
  111. aMin=vex[x].deep;
  112. }
  113. }
  114. g1[x].push_back(pg->v);//here!
  115. g1[pg->v].push_back(x);
  116. }
  117. }
  118. }
  119. }
  120. }
  121. }
  122. void Print(int u,bool *visited, int d)
  123. {
  124. printf("%d",u);
  125. if(d!=vexNum) printf(" ");
  126. visited[u]=1;
  127. if(u==1)
  128. {
  129. if(g1[1][1]<g1[1][0])
  130. {
  131. for(int i=1;i>=0;i–)
  132. if(!visited[g1[1][i]])
  133. Print(g1[1][i],visited, d+1);
  134. }
  135. else
  136. {
  137. for(int i=0;i<=1;i++)
  138. if(!visited[g1[1][i]])
  139. Print(g1[1][i],visited, d+1);
  140. }
  141. }
  142. else
  143. {
  144. for(int i=0;i<=1;i++)
  145. if(!visited[g1[u][i]])
  146. Print(g1[u][i],visited, d+1);
  147. }
  148. }
  149. int main()
  150. {
  151. int aCase;
  152. scanf("%d",&aCase);
  153. while(aCase–)
  154. {
  155. CreatGraph();
  156. Solve();
  157. bool visited[N]={0};
  158. Print(1,visited, 1);
  159. printf("\n");
  160. }
  161. return 0;
  162. }
Advertisements