• <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 極限定律 閱讀(1357) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            日韩欧美亚洲综合久久| 久久精品国产亚洲AV香蕉| 国产 亚洲 欧美 另类 久久| 国产69精品久久久久9999| 久久精品这里只有精99品| 久久人人爽人人爽人人av东京热| 精品国产青草久久久久福利| 久久久久久久97| 国产精品欧美亚洲韩国日本久久| 色播久久人人爽人人爽人人片aV| 一本色道久久88精品综合| 94久久国产乱子伦精品免费| 久久久黄色大片| 亚洲精品乱码久久久久久蜜桃不卡| 久久久久AV综合网成人| 精品久久久久久久久久中文字幕 | 性高湖久久久久久久久| 久久精品成人国产午夜| 狠狠色丁香久久婷婷综合蜜芽五月 | 久久99久久无码毛片一区二区| 国产成人精品三上悠亚久久| 久久www免费人成看国产片| 久久人人妻人人爽人人爽| 性高朝久久久久久久久久| 欧美久久精品一级c片片| 无码人妻久久一区二区三区 | 中文字幕无码精品亚洲资源网久久| 一本久久a久久精品综合夜夜| 久久偷看各类wc女厕嘘嘘| 欧美亚洲国产精品久久高清| 国产精品美女久久久久AV福利| 久久国产精品成人影院| 97精品国产97久久久久久免费| 久久久久亚洲精品天堂久久久久久| 久久精品草草草| 99国内精品久久久久久久| 亚洲国产精久久久久久久| 热re99久久精品国产99热| 久久精品www| 精品欧美一区二区三区久久久| 国产综合免费精品久久久|