題目大意：
一些學(xué)校連成了網(wǎng)絡(luò)， 在學(xué)校之間存在某個(gè)協(xié)議:每個(gè)學(xué)校都維護(hù)一張傳送表，表明他們要負(fù)責(zé)將收到的軟件傳送到表中的所有學(xué)校。如果A在B的表中，那么B不一定在A的表中。
現(xiàn)在的任務(wù)就是，給出所有學(xué)校及他們維護(hù)的表，問(wèn)1、如果所有學(xué)校都要被傳送到，那么需要幾份軟件備份；2、如果只用一份軟件備份，那么需要添加幾條邊？
題解：
1.即求強(qiáng)聯(lián)通分量的個(gè)數(shù)，或者說(shuō)是縮點(diǎn)以后入度為0的個(gè)數(shù)。
2.所有學(xué)校都連成一個(gè)強(qiáng)聯(lián)通分量，只需要將圖中的強(qiáng)聯(lián)通分量互相之間聯(lián)通就好了。添加的邊數(shù)就是縮點(diǎn)后入度為0的點(diǎn)和出度為0的點(diǎn)的最大值。

#include <stdio.h> #include <string.h> #include <queue> using namespace std;#define MAXN 110 #define INF 0x3f3f3f3f int n; int map[MAXN][MAXN]; int low[MAXN]; int dfn[MAXN]; int stack[MAXN], head; int instack[MAXN]; int belong[MAXN]; int in[MAXN]; int out[MAXN]; int index, cnt;int min(int a, int b) {return a < b ? a : b; }int max(int a, int b) {return a > b ? a : b; }void init() {int i, j;int temp;memset(map, 0, sizeof(map));memset(dfn, -1, sizeof(dfn));memset(low, 0, sizeof(low));memset(instack, 0, sizeof(instack));index = cnt = 1;head = 0;for(i= 1; i <= n; i++){while(scanf("%d", &temp) && temp){map[i][temp] = 1;}} } void tarjan(int x) {int i, a;low[x] = dfn[x] = index; // 剛搜到一個(gè)節(jié)點(diǎn)時(shí)low = dfnindex++;stack[++head] = x; // 將該節(jié)點(diǎn)入棧 instack[x] = 1; // 將入棧標(biāo)記設(shè)置為1for(i = 1; i <= n; i++) // 遍歷入棧節(jié)點(diǎn)的邊{if(!map[x][i]) // 如果兩點(diǎn)之間沒(méi)有邊continue; // 不用管它if(dfn[i] == -1) // 如果新搜索到的節(jié)點(diǎn)是從未被搜索過(guò){tarjan(i); // 那自然就得搜索這個(gè)節(jié)點(diǎn)low[x] = min(low[x], low[i]); // 回溯的時(shí)候改變當(dāng)前節(jié)點(diǎn)的low值 }else if(instack[i]) // 如果新搜索到的節(jié)點(diǎn)已經(jīng)被搜索過(guò)而且現(xiàn)在在棧中 {low[x] = min(low[x], dfn[i]); // 更新當(dāng)前節(jié)點(diǎn)的low值，這里的意思是兩個(gè)節(jié)點(diǎn)之間有一條可達(dá)邊，而前面 } // 而前面節(jié)點(diǎn)已經(jīng)在棧中，那么后面的節(jié)點(diǎn)就可能和前面的節(jié)點(diǎn)在一個(gè)聯(lián)通分量中 } if(low[x] == dfn[x]) // 最終退回來(lái)的時(shí)候 low == dfn ， 沒(méi)有節(jié)點(diǎn)能將根節(jié)點(diǎn)更新，那 { // low == dfn 的節(jié)點(diǎn)必然就是根節(jié)點(diǎn)int temp; while(1) // 一直出棧到此節(jié)點(diǎn)， 這些元素是一個(gè)強(qiáng)聯(lián)通分量 {temp = stack[head--]; // 彈出棧元素 belong[temp] = cnt; // 為了方便計(jì)算，將強(qiáng)聯(lián)通分量進(jìn)行標(biāo)記instack[temp] = 0; // 將棧內(nèi)標(biāo)記置為0 if(temp == x) // 一直彈到x出現(xiàn)為止 break;}cnt++;} } void solve() {int i, j;int t1, t2;while(scanf("%d", &n) != EOF) //{init(); // 初始化 for(i = 1; i <= n; i++) // if(dfn[i] == -1) // 如果某點(diǎn)沒(méi)被訪問(wèn)過(guò)，則對(duì)其進(jìn)行tarjan tarjan(i); // tarjan的成果是得到了一個(gè)belong數(shù)組，記錄每個(gè)節(jié)點(diǎn)分別屬于哪個(gè)強(qiáng)聯(lián)通分量 **for(i = 1; i <= n; i++) // 遍歷每條邊，找到縮點(diǎn)之后的邊 {for(j = 1;j <= n; j++){if(map[i][j] && belong[i] != belong[j]) // 兩點(diǎn)之間有邊，但不是屬于一個(gè)強(qiáng)聯(lián)通分量的邊{out[belong[i]]++; // 縮點(diǎn)后的點(diǎn)入度+1 in[belong[j]]++;// 縮點(diǎn)后的點(diǎn)出度+1 } } }** //縮點(diǎn)t1 = 0, t2 = 0;for(i = 1; i < cnt; i++){if(in[i] == 0)t1++;if(out[i] == 0)t2++;}if(cnt == 2)printf("1\n0\n");elseprintf("%d\n%d\n", t1, max(t1, t2));//縮點(diǎn)后入度為0的點(diǎn)和出度為0的點(diǎn)的最大值} }int main() { #ifdef LOCALfreopen("poj1236.txt", "r", stdin);// freopen(".txt", "w", stdout); #endifsolve();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/luckycode/p/5255650.html

總結(jié)

以上是生活随笔為你收集整理的poj1236-Tarjan算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。