題意：
? ? ? 一些學校有一個發送消息的體系，現在給你一些可以直接發送消息的一些關系（單向）然后有兩個問題
（1） 問你至少向多少個學校發送消息可以讓所有的學校都得到消息
（2） 問至少加多少條邊可以讓所有學校達到消息互通（變成強連通圖）


思路：
? ? ? 比較簡單了，我們先強連通所點，然后對于第一個問題，我們只要輸出入度為0的個數，這個很好理解，對于第二個問題，我們可以輸出max(入度為0的個數，出度為0的個數)，這樣做是因為我們可以吧度數大的先用小的補充上，剩下的就隨意補充就行了，還有就是記得只有一個聯通分量的時候特判一下，

PS ：假如這個題目要是讓輸出解決方案的話也比較好弄，對于第一個，每個入度為0的點給一個，每個強連通分量《元素個數大于1的》給一個就行了。對于第二個，就是先用小的填充大的，剩下的零頭隨意安排。

#include<stdio.h> #include<string.h> #include<stack>#define N_node 100 + 10 #define N_edge 10000 + 100using namespace std;typedef struct {int to ,next; }STAR;typedef struct {int a ,b; }EDGE;EDGE edge[N_edge]; STAR E1[N_edge] ,E2[N_edge]; int list1[N_node] ,list2[N_node] ,tot; int Belong[N_node] ,Cnt; int mark[N_node]; stack<int>sk;void add(int a ,int b) {E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot; }void DFS1(int s) {mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next){int to = E1[k].to;if(mark[to]) continue;mark[to] = 1;DFS1(to);}sk.push(s); }void DFS2(int s) {mark[s] = 1;Belong[s] = Cnt;for(int k = list2[s] ;k ;k = E2[k].next){int to = E2[k].to;if(mark[to]) continue;mark[to] =1;DFS2(to);} }int main () {int n ,i ,j ,a;while(~scanf("%d" ,&n)){memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;int nowid = 0;for(i = 1 ;i <= n ;i ++){while(scanf("%d" ,&a) && a){add(i ,a);edge[++nowid].a = i;edge[nowid].b = a;}}memset(mark ,0 ,sizeof(mark));while(!sk.empty()) sk.pop();for(i = 1 ;i <= n ;i ++){if(!mark[i]) DFS1(i);}Cnt = 0;memset(mark ,0 ,sizeof(mark));while(!sk.empty()){int xin = sk.top();sk.pop();if(mark[xin]) continue;Cnt ++;DFS2(xin);}int d1[N_node] = {0};int d2[N_node] = {0};for(i = 1 ;i <= nowid ;i ++){int a = Belong[edge[i].a];int b = Belong[edge[i].b];if(a == b) continue;d1[a] ++ ,d2[b] ++;}int sum1 = 0 ,sum2 = 0;for(i = 1 ;i <= Cnt ;i ++){if(!d1[i]) sum1 ++;if(!d2[i]) sum2 ++;}if(Cnt == 1){printf("1\n0\n");continue;}printf("%d\n" ,sum2);sum1 > sum2 ? printf("%d\n" ,sum1) : printf("%d\n" ,sum2);}return 0; }

總結

以上是生活随笔為你收集整理的POJ1236 强连通 （缩点后度数的应用）的全部內容，希望文章能夠幫你解決所遇到的問題。

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