hopcroft演算法
㈠ 學習數據結構，有哪些值得推薦的好書
作者：向小剛
鏈接：https://www.hu.com/question/19987046/answer/13945644
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請註明出處。
1. CLRS 演算法導論
演算法網路全書，只做了前面十幾章的習題，便感覺受益無窮。
2. Algorithms 演算法概論
短小精悍，別據一格，准經典之作。一個壞消息: 同演算法導論，該書沒有習題答案。好消息：習題很經典，難度也適中，只需花點點時間自己也都能做出來。不好也不壞的消息：我正在寫習題的答案，已完成前三章，還剩九章約二百道題，順利的話二個月之後發布。另有中文版名《演算法概論》，我沒看過，不知道翻譯得怎麼樣。如果有心的話，還是盡量看原版吧，其實看原版與看中文版花費時間不會相差很大，因為大部分時間其實都花費在做習題上了。
dr. dobb's essential books on Algorithm and daba structure
3. Algorithm Design 演算法設計
很經典的一本書，很久之前看的，遺憾的是現在除了就記得它很經典之外其它都忘光了。
4. SICP 計算機程序的構造和解釋
六星之書無需多言，雖然這不是一本講演算法的書，但看完此書有助於你更深入的理解什麼是遞歸。我一直很強調習題，看完此書後你至少應該做完前四章的太部分習題。否則那是你的遺憾，也是作者的遺憾。
5. Concrete Mathematics 具體數學
有人說看TAOCP之前應該先弄清楚這本書的內容，要真是如此的話那我恐怕是看不到TAOCP了。零零碎碎的看了一大半，很多東西都沒有時間來好好消化。如果你是剛進大學不久的本科生，有著大把的可自由支配時間，那你幸運又幸福了，花上幾個月時間好好的讀一下此書吧，收獲絕對大於你的期望值。
6. Introction to The Design and Analysis of Algorithms 演算法設計與分析基礎
很有趣的一本演算法書，有許多在別的書上找不到的趣題，看完此書絕對能讓你大開眼界，實在是一本居家旅行，面試裝逼的必備佳作。
7. 編程之美--微軟技術面試心得
雖說是一本面試書，但如果把前面十幾頁扯掉的話，我更願意把它看作是一本講解題思維的演算法小品。在書中，作者通常是給出一個平常解法，然後再一次又一次的優化改進，你可以很清楚的看到基本的演算法設計思想是如何得到運用以解決實際問題的。如果你已經有了一些演算法的基礎，看完本書應該能使你的演算法應用能力得到一定的提高。另外，本書生動有趣，也同樣適合於初學者。
8. Fundamentals of Algorithmics 演算法基礎
也是很久之前在學校圖書館借來看的，內容記不太清楚了，只隱約記得此書的動態規劃章節猶為出彩。應該是很經典的一本書，個人以為足以和演算法導論等所謂當世經典平分秋色，但是怎麼好像被人提到的不多，或許是我孤陋寡聞了。
9. How to solve it 怎樣解題
二十世紀最偉大的數學思想家之一波利亞的力作，講一般性的解題方法：怎麼認識問題，怎麼轉換問題，怎麼解決問題，如何在問題中得到啟發，如何找到一個通往答案的方向。
10. Programming interviews exposed 程序員面試攻略
一本消遣之作。個人以為要比國內的某「XXX面試寶典」純粹一些，至少也有一些啟發性的內容，而不單單是面試題解庫。
11. Programming Pearls 編程珠璣
學習演算法不僅需要像Alogrithms，演算法導論這樣的重量級的內功心法，像《編程之美》、《編程珠璣》這樣的輕量級的輕功身法也必不可少。前些年網上不是很流行像「給你10億個數，找到最大的n個」或者「給你10億個數，找出現次數最多的那個數」之類的網路面試題嗎？看了此書你就知道怎麼解決了。相比於《編程之美》來說，本書中的示例技巧性略低一些，但是也更有實際應用價值一些。
12. 演算法藝術與信息學競賽
如果演算法導論是九陽神功，那這本無疑就是九陰真經。本書是專為參加一些諸如ACM之類程序設計比賽的同學而寫的，江湖人稱「黑書」。裡面講的都是一些在編程比賽中常用的演算法、數據結構，以及一些數論和計算幾何等。我雖然並不搞競賽，但也從此書中受益頗多。
13. An Introction to Probability Theory and Its Applications
准備看的，現在才發現概率論有多麼重要，可惜本科的時候沒有好好學。前不久一個同學問我個問題，我半天弄了一個程序給他，他說：這里就不是相關系數么，Excel一下就完事！我暈，我還真不知道那就是相關系數。
14. Numerical Analysis
這本的作者是Richard L. Burden,J. Douglas Faires
數值分析，討論各種數值演算法，比如插值、擬合、積分、微分方程的求解、線性和非線性方程組求解等。准備詳細看。
15. TAOCP 計算機程序設計藝術
傳說中的TAOCP，說的人多，看的人少。TAOCP四卷堪稱是演算法藏經閣中的易筋經或者是少林七十二絕技。天下武學，盡出少林，天下演算法，盡出TAOCP也。
㈡ 二分圖最大匹配的Hopcroft-Carp演算法的pascal實現，求各神牛，懸賞！！！！
program hopcroft_karp;
const maxn=100;
var linkx, linky, distx, disty, queue: array[1..maxn] of longint; //link表示已經匹配的邊 x為左 y為右
map: array[1..maxn, 1..maxn] of boolean;
n, m, i, x, y, ans: longint;
function bfs: boolean;
var i, now, head, tail: longint;
begin
fillchar(distx,sizeof(distx),0); //dist表示該點在增廣路中被搜到時的距離
fillchar(disty,sizeof(disty),0);
bfs:=false;
head:=0; tail:=0;
for i:=1 to n do if (linkx[i]=0) then begin
inc(tail);
queue[tail]:=i;
end;
while (head<tail) do begin //利用隊列搜索增廣路
inc(head); now:=queue[head];
for i:=1 to n do if map[now,i] and (disty[i]=0) then begin //disty[i]<>0: 增廣路不能交叉
disty[i]:=distx[now]+1;
if (linky[i]=0) then bfs:=true
else begin //左邊的點無須判斷dist是否為0
distx[linky[i]]:=disty[i]+1;
inc(tail);
queue[tail]:=linky[i]; //queue只記錄左邊的點
end;
end;
end;
end;
function dfs(x:longint): boolean;
var i: longint;
begin
for i:=1 to n do if map[x,i] and (disty[i]=distx[x]+1) then begin //為了判斷是否能形成增廣路
disty[i]:=0; //dist改為0 防止下次再搜到此點 由於這個條件可能導致增廣路轉道
if (linky[i]=0) or dfs(linky[i]) then begin //有時候會使原來搜索到的一些增廣路無法繼續更新
linkx[x]:=i; //但是不會出現錯誤
linky[i]:=x; //DFS過程類似hungry演算法
exit(true);
end;
end;
exit(false);
end;
begin
fillchar(map,sizeof(map),false);
read(n,m);
for i:=1 to m do begin
read(x,y);
map[x,y]:=true; //map不能賦雙向值
end;
fillchar(linkx,sizeof(linkx),0);
fillchar(linky,sizeof(linky),0);
ans:=0;
while bfs do
for i:=1 to n do
if (linkx[i]=0) and dfs(i) then inc(ans);
writeln(ans);
end.
思路：首先用bfs判斷圖中是否有增廣路，如果有，則利用dist記錄下來，然後用dfs處理增廣路，不斷循環直到不存在增廣路
由於bfs一次可以判斷出許多增廣路，演算法會比hungry快很多，hungry的復雜度為n*m，而hopcroft的復雜度為n^0.5*m