• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            POJ 1236 Network of Schools 強連通分量+縮點

             

            Description

            A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
            You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.

            Input

            The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

            Output

            Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

            Sample Input

            5
            2 4 3 0
            4 5 0
            0
            0
            1 0
            

            Sample Output

            1
            2
            

            Source

               

            題目大意:N(2<N<100)各學校之間有單向的網絡,每個學校得到一套軟件后,可以通過單向網絡向周邊的學校傳輸,問題1:初始至少需要向多少個學校發放軟件,使得網絡內所有的學校最終都能得到軟件。2,至少需要添加幾條傳輸線路(邊),使任意向一個學校發放軟件后,經過若干次傳送,網絡內所有的學校最終都能得到軟件。

            具體算法:先用Korasaju Algorithm求出有向圖所有的強連通分量,然后將所有的強連通分量縮成一個點(縮點),這樣原來的有向圖就縮成了一個DAG圖(有向無環圖);用2個數組分別記錄新生成的DAG圖中的每個頂點(包括原來的頂點和強連通分量的縮點)是否有出邊和入邊,最后遍歷每個頂點,如果沒有入邊,則ans1++;如果沒有出邊,ans2++。最后所求即為ans1和max(ans1,ans2)。
            #include <iostream>
            #include 
            <vector>
            using namespace std;

            const int MAXN = 101;
            int n,m,cnt;
            bool visit[MAXN];
            int set[MAXN],order[MAXN],in[MAXN],out[MAXN];
            vector
            < vector<int> > adj;
            vector
            < vector<int> > radj;

            void dfs(int u){
                visit[u]
            =true;
                
            int i,len=adj[u].size();
                
            for(i=0;i<len;i++)
                    
            if(!visit[adj[u][i]])
                        dfs(adj[u][i]);
                order[cnt
            ++]=u;
            }

            void rdfs(int u){
                visit[u]
            =true;
                
            set[u]=cnt;
                
            int i,len=radj[u].size();
                
            for(i=0;i<len;i++)
                    
            if(!visit[radj[u][i]])
                        rdfs(radj[u][i]);
            }

            void korasaju(){
                
            int i;
                memset(visit,
            false,sizeof(visit));
                
            for(cnt=0,i=1;i<=n;i++)
                    
            if(!visit[i])
                        dfs(i);
                memset(visit,
            false,sizeof(visit));
                
            for(cnt=0,i=n-1;i>=0;i--)
                    
            if(!visit[order[i]])
                        cnt
            ++,rdfs(order[i]);
            }

            int main(){
                
            int i,j;
                scanf(
            "%d",&n);
                adj.assign(n
            +1,vector<int>());
                radj.assign(n
            +1,vector<int>());
                
            for(i=1;i<=n;i++){
                    
            while(scanf("%d",&m),m){
                        adj[i].push_back(m);
                        radj[m].push_back(i);
                    }

                }

                korasaju();
                memset(
            in,1,sizeof(in));
                memset(
            out,1,sizeof(out));
                
            for(i=1;i<=n;i++)
                    
            for(j=0;j<adj[i].size();j++)
                        
            if(set[i]!=set[adj[i][j]]){
                            
            out[set[i]]=0;
                            
            in[set[adj[i][j]]]=0;
                        }

                
            int ans1=0,ans2=0;
                
            for(i=1;i<=cnt;i++){
                    
            if(out[i]) ans2++;
                    
            if(in[i]) ans1++;
                }

                
            if(cnt==1){
                    printf(
            "1\n");
                    printf(
            "0\n");
                }

                
            else{
                    printf(
            "%d\n",ans1);
                    printf(
            "%d\n",max(ans1,ans2));
                }

                
            return 0;
            }

            posted on 2009-05-25 16:21 極限定律 閱讀(1354) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            99热都是精品久久久久久| 看全色黄大色大片免费久久久| 久久久久免费精品国产| 久久精品国产亚洲AV无码娇色| 9久久9久久精品| 色欲综合久久躁天天躁| 无码AV波多野结衣久久| 久久精品无码一区二区三区| 久久久精品无码专区不卡| 久久天天躁夜夜躁狠狠躁2022| 99久久久精品| 亚洲精品国精品久久99热| 久久精品国产网红主播| 蜜桃麻豆www久久国产精品| 国产成人精品白浆久久69| 久久中文字幕无码专区| 久久精品a亚洲国产v高清不卡| 久久亚洲av无码精品浪潮| 久久99国产综合精品| 99久久做夜夜爱天天做精品| 国产无套内射久久久国产| 久久亚洲精品无码AV红樱桃| 亚洲日本va午夜中文字幕久久| 97精品国产97久久久久久免费| 人妻精品久久久久中文字幕69| 中文字幕精品久久| 香蕉久久影院| 亚洲国产成人久久精品99| 99精品伊人久久久大香线蕉| 久久丫精品国产亚洲av不卡| 久久无码专区国产精品发布| 久久亚洲国产精品123区| 久久99久久成人免费播放| 88久久精品无码一区二区毛片| 蜜臀av性久久久久蜜臀aⅴ| 99久久免费国产精品特黄| 亚洲欧美日韩精品久久亚洲区 | 一级女性全黄久久生活片免费| 四虎国产精品免费久久久| 国产精品久久精品| 色偷偷888欧美精品久久久|