這次的解題報告是有關tarjan演算法的一道思維量比較大的題目（真的是原創文章，希望管理員不要再把文章移出首頁）。 這道題蒟蒻以前做過，但是今天由於要複習tarjan演算法，於是就看到codevs分類強聯通分量裡面只有這一道題。 題目是這樣的： 這是一個有向圖上的問題，這道題很容易看出來一個愛心天使就是 ...
這次的解題報告是有關tarjan演算法的一道思維量比較大的題目（真的是原創文章，希望管理員不要再把文章移出首頁）。
這道題蒟蒻以前做過，但是今天由於要複習tarjan演算法，於是就看到codevs分類強聯通分量裡面只有這一道題。
題目是這樣的：
“每個人都擁有一個夢，即使彼此不相同，能夠與你分享，無論失敗成功都會感動。愛因為在心中，平凡而不平庸，世界就像迷宮，卻又讓我們此刻相逢Our Home。” 在愛的國度里有N個人，在他們的心中都有著一個愛的名單，上面記載著他所愛的人（不會出現自愛的情況）。愛是具有傳遞性的，即如果A愛B，B愛C，則A也愛C。 如果有這樣一部分人，他們彼此都相愛，則他們就超越了一切的限制，用集體的愛化身成為一個愛心天使。 現在，我們想知道在這個愛的國度里會出現多少愛心天使。而且，如果某個愛心天使被其他所有人或愛心天使所愛則請輸出這個愛心天使是由哪些人構成的，否則輸出-1。
這是一個有向圖上的問題，這道題很容易看出來一個愛心天使就是一群人互相愛然後組成的有向環。既然是有向的圖求強聯通分量，套上tarjan就行了。不過因為後面要輸出愛心天使是由哪些人構成的，所以，我們需要記錄每個人在哪個愛心天使裡面，具體tarjan標程就是下麵這樣：
1 void dfs(int u){ 2 low[u] = dfn[u] = ++dfs_clock; 3 s.push(u); 4 for(int i = 0;i < g[u].size();++i){ 5 int v = g[u][i]; 6 if(!dfn[v]){ 7 dfs(v); 8 low[u] = min(low[u],low[v]); 9 } 10 else if(!ind[v]){ 11 low[u] = min(low[u],dfn[v]); 12 } 13 } 14 if(low[u] == dfn[u]){ 15 scc_cnt++; 16 while(1){ 17 int x = s.top(); 18 s.pop(); 19 ind[x] = scc_cnt; 20 sccno[scc_cnt]++; 21 if(x == u)break; 22 } 23 } 24 } 25 void find_scc(int n){ 26 dfs_clock = scc_cnt = 0; 27 for(int i = 1;i <= n;++i){ 28 if(!dfn[i])dfs(i); 29 } 30 }
如果有不懂的地方，就說明是tarjan演算法還是沒搞懂，請先搞定tarjan演算法的基礎再來看這道題。
然後就是求每個愛心天使被多少個人愛著（愛心天使也被屬於它自己的人們愛著）。由於愛有傳遞性，我們很容易能想到傳遞閉包的問題。具體做法就是：
1.先求出來所有的愛心天使（在這裡一個人也當作是一個愛心天使，但是輸出愛心天使個數的時候，一個人組成的愛心天使是不算的）和這個愛心天使由多少個人組成。
2.給每個愛心天使編號（縮點），然後建立一個以“被愛”為方向的新的有向圖。
3.在新的有向圖中跑SPFA（為什麼不用Floyd，這個時間複雜度太高了，所以我們還是選擇scc_cnt遍的SPFA，時間複雜度最壞也就是O（nke），保證是超不了時間的。SPFA在這裡起到的作用就是計算每個愛心天使的愛能否傳遞到某個天使）。
4.統計計數，如果size[某個愛心天使] == n的話，那麼就按編號從小到大遍歷每個人輸出這個愛心天使由哪些人組成。如果沒有任何一個愛心天使的size為n的話，（用一個數記錄，如果b == 0）就輸出-1.
然後呈現整體代碼，還是不是很長，才剛139行。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 #include <stack> 7 #include <vector> 8 #include <set> 9 #include <queue> 10 using namespace std; 11 const int maxn = 1005; 12 int dfn[maxn],low[maxn],dfs_clock,n,ind[maxn],m,scc_cnt,a,b,size[maxn],sccno[maxn],tim = 0; 13 struct edge{ 14 int u,v; 15 edge(int a,int b):u(a),v(b){}; 16 }; 17 struct edges{ 18 int to,next,cost; 19 }qmap[maxn<<3]; 20 vector<int>g[maxn]; 21 vector<int>gk[maxn]; 22 vector<edge>ga; 23 int d[maxn],h[maxn]; 24 const int INF = 10000000; 25 stack<int> s; 26 void add(int u,int v){ 27 qmap[tim].to = v;qmap[tim].cost = 1;qmap[tim].next = h[u];h[u] = tim++; 28 } 29 void init(int n){ 30 memset(dfn,0,sizeof(dfn)); 31 memset(low,0,sizeof(low)); 32 memset(ind,0,sizeof(ind)); 33 memset(size,0,sizeof(size)); 34 memset(sccno,0,sizeof(sccno)); 35 memset(h,-1,sizeof(h)); 36 for(int i = 1;i <= n;++i){ 37 g[i].clear(); 38 gk[i].clear(); 39 } 40 } 41 void dfs(int u){ 42 low[u] = dfn[u] = ++dfs_clock; 43 s.push(u); 44 for(int i = 0;i < g[u].size();++i){ 45 int v = g[u][i]; 46 if(!dfn[v]){ 47 dfs(v); 48 low[u] = min(low[u],low[v]); 49 } 50 else if(!ind[v]){ 51 low[u] = min(low[u],dfn[v]); 52 } 53 } 54 if(low[u] == dfn[u]){ 55 scc_cnt++; 56 while(1){ 57 int x = s.top(); 58 s.pop(); 59 ind[x] = scc_cnt; 60 sccno[scc_cnt]++; 61 if(x == u)break; 62 } 63 } 64 } 65 void find_scc(int n){ 66 dfs_clock = scc_cnt = 0; 67 for(int i = 1;i <= n;++i){ 68 if(!dfn[i])dfs(i); 69 } 70 } 71 void spfa(int x){ 72 for(int i = 1;i <= scc_cnt;++i){ 73 d[i] = INF; 74 } 75 bool visit[maxn]; 76 memset(visit,false,sizeof(visit)); 77 d[x] = 0; 78 queue<int>q; 79 q.push(x); 80 visit[x] = true; 81 while(!q.empty()){ 82 int y = q.front(); 83 q.pop();visit[y] = false; 84 for(int i = h[y];i != -1;i = qmap[i].next){ 85 edges e = qmap[i]; 86 if(d[y] + e.cost < d[e.to]){ 87 d[e.to] = d[y] + e.cost; 88 if(!visit[e.to]){ 89 q.push(e.to); 90 visit[e.to] = true; 91 } 92 } 93 } 94 } 95 } 96 void work(int i){ 97 spfa(i); 98 for(int k = 1;k <= scc_cnt;++k){ 99 if(k == i)continue; 100 if(d[k] == INF)continue; 101 size[i] += sccno[k]; 102 } 103 if(size[i] == n){ 104 b = 1; 105 for(int j = 1;j <= n;++j){ 106 if(ind[j] == i)printf("%d ",j); 107 } 108 printf("\n"); 109 } 110 return; 111 } 112 int main(){ 113 scanf("%d%d",&n,&m); 114 init(n); 115 for(int i = 1;i <= m;++i){ 116 scanf("%d%d",&a,&b); 117 g[a].push_back(b); 118 gk[b].push_back(a); 119 ga.push_back(edge(b,a)); 120 } 121 find_scc(n); 122 int ans = scc_cnt; 123 for(int i = 1;i <= scc_cnt;++i){ 124 if(sccno[i] == 1)ans--; 125 } 126 printf("%d\n",ans); 127 for(int i = 0;i < ga.size();++i){ 128 add(ind[ga[i].u],ind[ga[i].v]); 129 } 130 for(int i = 1;i <= scc_cnt;++i){ 131 size[i] = sccno[i]; 132 } 133 b = 0; 134 for(int i = 1;i <= scc_cnt;++i){ 135 if(sccno[i] != 1)work(i); 136 } 137 if(b == 0)printf("-1\n"); 138 return 0; 139 }
這次的解題報告就到這裡，蒟蒻繼續去刷題了。還有如果有問題的話，請聯繫我的郵箱[email protected]向我留言。
