題目描述：
有一些學校連接到一個計算機網絡。這些學校之間達成了一個協議：每個學校維護著一個學
校列表，它向學校列表中的學校發布軟件。注意，如果學校B在學校A的列表中，則A不一定在
B的列表中。
任務A：計算為使得每個學校都能通過網絡收到軟件，你至少需要準備多少份軟件拷貝。
任務B：考慮一個更長遠的任務，想確保給任意一個學校發放一個新的軟件拷貝，該軟件拷
貝能發布到網絡中的每個學校。為了達到這個目標，必須在列表中增加新成員。計算需要添加新
成員的最小數目。
// 任務A就是求縮點后 入度為0的點的個數

// 任務B 就是讓縮點后的圖中出度或入度為0的點消失 那么只要出度為0的點和入度為0的點連 主要看哪種點多就是了
#include <iostream> #include <algorithm> #include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <string.h> using namespace std; #define MOD 1000000007 #define maxn 60100 #define maxm 10010 struct Edge{int to;int next;Edge(){};Edge(int u,int v){to=u;next=v;} }E[maxn]; stack<int> S; int V[maxm],num; int belong[maxm]; int pre[maxm]; int dfst,scc; int ans; bool tag[maxm]; int in[maxm],out[maxm]; void init(int n){dfst=scc=0;num=0;ans=0;while(!S.empty())S.pop();for(int i=1;i<=n;i++){V[i]=-1;pre[i]=0;belong[i]=0;} } void add(int u,int v){E[num].to=v;E[num].next=V[u];V[u]=num++; } int tarjan(int u){int lowu=pre[u]=++dfst;int v,e;S.push(u);for(e=V[u];e!=-1;e=E[e].next){v=E[e].to;if(!pre[v]){int lowv=tarjan(v);lowu=min(lowu,lowv);}else if(!belong[v]) lowu=min(lowu,pre[v]);}if(lowu==pre[u]){scc++;for(;;){int x=S.top();S.pop();belong[x]=scc;if(x==u) break;}}return lowu; } int main() {int n,m,T;int u,v;int i,j=1;//scanf("%d",&T);while(scanf("%d",&n)!=EOF){// scanf("%d",&m); init(n);for(i=1;i<=n;i++){u=i;while(scanf("%d",&v),v){add(u,v);}}for(i=1;i<=n;i++)if(!pre[i]) tarjan(i);// for(i=1;i<=n;i++) printf("%d ",belong[i]);for(i=1;i<=scc;i++) out[i]=0,in[i]=0;int e,u,v;for(i=1;i<=n;i++){for(e=V[i];e!=-1;e=E[e].next){u=belong[i];v=belong[E[e].to];if(u!=v){in[v]++;out[u]++;//,printf("v=%d ",v);}
}}int A=0,B=0;for(i=1;i<=scc;i++){if(!in[i]) A++;if(!out[i]) B++;}B=max(A,B);if(scc==1) B=0;// 特殊情況下 只有一個強連通分量 郁悶開始這里寫成了nprintf("%d\n%d\n",A,B);}return 0; }

?

轉載于:https://www.cnblogs.com/372465774y/p/3205747.html

總結

以上是生活随笔為你收集整理的poj 1236 Network of Schools的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。