題目大意：

N個學(xué)校之間有單向的網(wǎng)絡(luò)，每個學(xué)校得到一套軟件后，可以通過單向網(wǎng)絡(luò)向周邊的學(xué)校傳輸。問題1：初始至少需要向多少個學(xué)校發(fā)放軟件，使得網(wǎng)絡(luò)內(nèi)所有的學(xué)校最終都能得到軟件。問題2：至少需要添加幾條傳輸線路(邊)，使任意向一個學(xué)校發(fā)放軟件后，經(jīng)過若干次傳送，網(wǎng)絡(luò)內(nèi)所有的學(xué)校最終都能得到軟件。

鏈接http://vjudge.net/problem/viewProblem.action?id=17001

每個強(qiáng)連通分量內(nèi)只要有任意一個學(xué)校獲得一份軟件就可以了，因?yàn)閺?qiáng)連通分量內(nèi)的任意兩點(diǎn)是相互可達(dá)的。

也就是說，在一個強(qiáng)聯(lián)通分量內(nèi)的學(xué)?？梢援?dāng)作一個學(xué)校！

那么第一問我們所求的就是強(qiáng)連通分量重入度為零的點(diǎn)

而第二問因?yàn)閮蓚€強(qiáng)連通合并必然是出度為0的連接入度為0的點(diǎn)，所以要解決掉入度為0，和出度為0的點(diǎn)，所以答案是這兩個的最大值（點(diǎn)指縮點(diǎn)）。

利用scc[i]=scc_cnt 來記錄i這個點(diǎn)屬于scc_cnt這個連通分量

總代碼如下

#include <iostream> #include <cstdio> #include <cstring> #include <stack> using namespace std; #define N 105 int first[N],scc[N],dfn[N],low[N],degreeIn[N],degreeOut[N],k,n,tmpdfn,scc_cnt; stack<int> q; struct Path{int y,next; }path[100005]; void init() {memset(first,-1,sizeof(first));memset(dfn,0,sizeof(dfn));memset(degreeIn,0,sizeof(degreeIn));memset(degreeOut,0,sizeof(degreeOut));memset(scc,0,sizeof(scc));scc_cnt=0,tmpdfn=0,k=0; } void add(int x,int y) {path[k].y=y,path[k].next=first[x];first[x]=k;k++; } void dfs(int u) {dfn[u]=low[u]=++tmpdfn;q.push(u);for(int i=first[u];i!=-1;i=path[i].next){int v=path[i].y;if(!dfn[v]){dfs(v);low[u]=min(low[v],low[u]);}else if(!scc[v]) low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){scc_cnt++;for(;;){int v=q.top(); q.pop();scc[v]=scc_cnt;if(u==v) break;}} } void get_scc() {while(!q.empty()) q.pop();for(int i=1;i<=n;i++)if(!dfn[i]) dfs(i);//cout<<"OK"<<endl;for(int i=1;i<=n;i++){for(int j=first[i];j!=-1;j=path[j].next){int v=path[j].y;//cout<<v<<endl;if(scc[i]!=scc[v]){degreeOut[scc[i]]++;degreeIn[scc[v]]++;}}} } int main() {int i,a;while(~scanf("%d",&n)){int ans1=0,ans2=0;init();for(i=1;i<=n;i++){while(scanf("%d",&a) && a) add(i,a);}get_scc();//for(int i=1;i<=scc_cnt;i++) cout<<degreeIn[i]<<endl;//cout<<scc_cnt<<endl;for(int i=1;i<=scc_cnt;i++){if(!degreeOut[i]) ans1++;if(!degreeIn[i]) ans2++;}ans1=max(ans1,ans2);//cout<<"á?í¨·?á?￡o"<<cnt<<endl;if(scc_cnt>1){printf("%d\n",ans2);printf("%d\n",ans1);}else printf("1\n0\n");}return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的POJ 1236 学校网络间的强连通的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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