POJ 1515

题目大意：给出一副无向联通图，求把一些边改成有向边之后，整幅图还是为一个强连通分量。

p.s．一开始在本地做的，没读懂题意，其实是让你把边改有向而非删除边，好像要求改的数量最多，本地我提交了一个把边读入输出的程序本地spj过了= =，poj上wa了才真正想算法的。

解：我原意是把桥找出来，然后其他遍历，不过好像调错的样子。听说了fjy刷了个16ms p组第一，所以去参考了下，发现就是tarjan途中，桥输出双向，其他单向即可（因为tarjan就是在找一个最大的环），所以tarjan图中处理输出就行(注意横叉边也要输一次，也就是说除了输环，桥输双向，其他任意)，不过后来还是跑了32ms..

View Code

  1 //poj 1515
  2 const
  3         maxn=1011;
  4         maxm=maxn*4;
  5         inf='street.in';
  6         ouf='street.out';
  7 type
  8         type_edge=record
  9           st, dest, next, op: longint;
 10         end;
 11 var
 12         edge: array[0..maxm*2]of type_edge;
 13         vect, dfn, low: array[0..maxn]of longint;
 14         visit: array[0..maxn]of boolean;
 15         key: array[0..maxm*2]of boolean;
 16         test, edge_tot, n, m, stack_tot, time: longint;
 17 procedure add(x, y: longint);
 18 begin
 19   inc(edge_tot);
 20   with edge[edge_tot] do begin
 21     st := x;
 22     dest := y;
 23     next := vect[x];
 24     vect[x] := edge_tot;
 25     op := edge_tot+1;
 26   end;
 27   inc(edge_tot);
 28   with edge[edge_tot] do begin
 29     st := y;
 30     dest := x;
 31     next := vect[y];
 32     vect[y] := edge_tot;
 33     op := edge_tot - 1;
 34   end;
 35 end;
 36 
 37 procedure init;
 38 var
 39         i, x, y: longint;
 40 begin
 41   edge_tot := 0;
 42   fillchar(vect, sizeof(vect), 0);
 43   for i := 1 to m do begin
 44     readln(x, y);
 45     add(x, y);
 46   end;
 47 end;
 48 
 49 procedure dfs(x, pre: longint);
 50 var
 51         i, u, tmp: longint;
 52 begin
 53   inc(time);
 54   dfn[x] := time; low[x] := time;
 55   inc(stack_tot);
 56   visit[x] := true;
 57   i := vect[x];
 58   while i<>0 do
 59    with edge[i] do begin
 60     if (dest=pre) then begin
 61       i := next;
 62       continue;
 63     end;
 64     if (dfn[dest]=0) then begin
 65       writeln(st, ' ', dest);
 66       dfs(dest, x);
 67       if low[dest]<low[x] then low[x] := low[dest];
 68       if dfn[x]<low[dest] then
 69         writeln(edge[op].st, ' ', edge[op].dest);
 70     end
 71     else if visit[dest] then begin
 72       if dfn[dest]<low[x] then begin
 73         low[x] := dfn[dest];
 74       end;
 75       if key[i] then begin
 76         writeln(st, ' ', dest);
 77         key[op] := false;
 78       end;
 79     end;
 80     i := next;
 81   end;
 82 end;
 83 
 84 procedure main;
 85 begin
 86   fillchar(dfn, sizeof(dfn), 0);
 87   //fillchar(low, sizeof(low), 0);
 88   fillchar(visit, sizeof(visit), 0);
 89   //fillchar(pre, sizeof(pre), 0);
 90   fillchar(key, sizeof(key), true);
 91   time := 0;
 92   dfs(1, 0);
 93 end;
 94 
 95 begin
 96   assign(input,inf); reset(input);
 97   assign(output,ouf); rewrite(output);
 98   test := 0;
 99   readln(n, m);
100   while n+m<>0 do begin
101    inc(test);
102     writeln(test);
103     writeln;
104     init;
105     main;
106     writeln('#');
107     readln(n, m);
108   end;
109   close(input); close(output);
110 end.