• <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>

            Drolca

            Apologize To Drolca
            隨筆 - 28, 文章 - 1, 評論 - 6, 引用 - 0
            數(shù)據(jù)加載中……

            pku 1236 Network of Schools

             

            #include <iostream>
            using namespace std;
            #define init(I) memset(I,0,sizeof(I))
            const int maxn=101;
            struct edge
            {
                
            int data;
                edge 
            *next;
            }
            ;
            edge 
            *g1[maxn],*g2[maxn],*g[maxn];
            int vis[maxn],path[maxn],scc[maxn],mark[maxn][maxn];
            int out[maxn],in[maxn];
            int n,m,cnt;

            void add(edge* t[],int s,int e){
                edge 
            *p;
                p
            =new edge;
                p
            ->data=e;
                p
            ->next=t[s];
                t[s]
            =p;
            }


            void dfs1(int s){
                vis[s]
            =1;
                edge 
            *p;
                
            for(p=g1[s];p;p=p->next)
                    
            if(!vis[p->data])
                        dfs1(p
            ->data);
                path[
            0]++;
                path[path[
            0]]=s;
            }


            void dfs2(int s){
                vis[s]
            =1;
                scc[s]
            =scc[0];
                edge 
            *p;
                
            for(p=g2[s];p;p=p->next)
                    
            if(!vis[p->data])
                        dfs2(p
            ->data);    
            }


            void shrink(){
                
            int s,e,k;
                init(mark);
                edge 
            *p;
                
            for(k=1;k<=n;k++)
                    
            for(p=g1[k],s=scc[k];p;p=p->next)
                    
            {
                        e
            =scc[p->data];
                        
            if(s!=e&&!mark[s][e])
                        
            {
                            mark[s][e]
            =1;
                            add(g,s,e);
                        }

                    }

            }


            void kosaraju()
            {
                
            int i;
                path[
            0]=scc[0]=0;
                init(vis);
                
            for(i=1;i<=n;i++)
                    
            if(!vis[i])
                        dfs1(i);
                init(vis);
                
            for(i=n;i>=1;i--)
                
            {
                    
            if(!vis[path[i]])
                    
            {
                        scc[
            0]++;
                        dfs2(path[i]);
                    }

                }

            }

            int main()
            {
                
            int to,i,j;
                scanf(
            "%d",&n);
                
            for(i=1;i<=n;i++)
                    g1[i]
            =g2[i]=g[i]=NULL;
                
            for(i=1;i<=n;i++)
                
            {
                    
            while(scanf("%d",&to)&&to)
                    
            {
                        add(g1,i,to);
                        add(g2,to,i);
                    }

                }

                kosaraju();
                shrink();

                init(
            out);
                init(
            in);
                
            int cnt=scc[0];
                
                
            for(i=1;i<=cnt;i++)
                    
            for(j=1;j<=cnt;j++)
                        
            if(mark[i][j])
                        
            {
                            
            out[i]++;
                            
            in[j]++;
                        }

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

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

                printf(
            "%d\n",t1);
                printf(
            "%d\n",t1>t2?t1:t2);
                
            return 0;
            }

            posted on 2009-08-20 17:08 Drolca 閱讀(168) 評論(0)  編輯 收藏 引用

            久久精品国产亚洲精品2020 | 狠狠色婷婷久久一区二区三区| 国产精品一区二区久久精品| 久久天天躁夜夜躁狠狠躁2022| 伊人久久综合热线大杳蕉下载| 久久精品无码专区免费东京热| 一本一本久久a久久综合精品蜜桃| 国内精品久久久久影院亚洲| 天天做夜夜做久久做狠狠| 国产高清国内精品福利99久久| 丁香五月网久久综合| 国产精品久久久久久福利漫画 | 伊人久久五月天| 亚洲国产成人精品91久久久| 伊人久久一区二区三区无码| 亚洲国产成人精品女人久久久 | 久久综合偷偷噜噜噜色| 亚洲欧美成人综合久久久| 熟妇人妻久久中文字幕| 99久久人妻无码精品系列| 国产精品综合久久第一页| 久久五月精品中文字幕| 久久无码AV一区二区三区| 久久夜色精品国产噜噜噜亚洲AV | 狠色狠色狠狠色综合久久| 国产福利电影一区二区三区久久老子无码午夜伦不| 国内精品久久国产大陆| 久久久久久久久久久免费精品| 一级做a爰片久久毛片看看| 无码超乳爆乳中文字幕久久 | 久久精品中文闷骚内射| 国产亚洲色婷婷久久99精品91| 久久综合伊人77777麻豆| 亚洲va久久久噜噜噜久久天堂| 国产一久久香蕉国产线看观看| 久久久久久青草大香综合精品| 久久久久久精品成人免费图片| 91久久婷婷国产综合精品青草| 天堂无码久久综合东京热| 999久久久免费精品国产| 香蕉久久永久视频|