• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            設(shè)無(wú)向圖頂點(diǎn)個(gè)數(shù)為n,邊數(shù)為m。DFS遍歷無(wú)向圖,找到該無(wú)向圖連通分量的個(gè)數(shù)num,則冗余關(guān)系數(shù)為m-n+num。另外由于此題中頂點(diǎn)數(shù)較多而邊數(shù)較少,采用鄰接表存儲(chǔ),提高效率。
            以下是我的代碼:
            #include<iostream>
            #include
            <string.h>
            #define maxn 1007
            #define maxm 1007
            using namespace std;

            typedef 
            struct
            {
                
            long v,w;
            }edge;
            long n,m,num;
            long cnt,first[maxn],next[2*maxm];
            edge e[
            2*maxm];
            bool used[maxn];

            void dfs(long s)
            {
                used[s]
            =true;
                
            for(long i=first[s];i;i=next[i])
                    
            if(!used[e[i].v])
                        dfs(e[i].v);
            }

            int main()
            {
                memset(first,
            0,sizeof(first));
                memset(next,
            0,sizeof(next));
                memset(e,
            0,sizeof(e));
                
                cin
            >>m>>n;
                cnt
            =0;
                
            for(long i=1;i<=m;i++)
                {
                    
            long a,b;
                    cin
            >>a>>b;
                    cnt
            ++;e[cnt].v=b;
                    next[cnt]
            =first[a];
                    first[a]
            =cnt;
                    cnt
            ++;e[cnt].v=a;
                    next[cnt]
            =first[b];
                    first[b]
            =cnt;
                }
                
            //  Input
                
                num
            =0;
                memset(used,
            false,sizeof(used));
                
            for(long i=1;i<=n;i++)
                    
            if(!used[i])
                    {
                        num
            ++;
                        dfs(i);
                    }
                
            //  DFS
                
                cout
            <<m-n+num<<endl;
                
            //  Output
            return 0;
            }
            posted on 2010-10-18 15:38 lee1r 閱讀(313) 評(píng)論(1)  編輯 收藏 引用 所屬分類: 題目分類:圖論

            FeedBack:
            # re: tyvj P1017 冗余關(guān)系
            2012-09-09 14:35 | spix
            經(jīng)典阿  回復(fù)  更多評(píng)論
              
            天天久久狠狠色综合| …久久精品99久久香蕉国产| 久久91亚洲人成电影网站| 久久综合狠狠综合久久综合88 | 夜夜亚洲天天久久| 久久精品国产亚洲av水果派| 久久天天躁狠狠躁夜夜2020一| 久久精品视屏| 波多野结衣久久精品| 国产精品美女久久福利网站| 狠狠综合久久AV一区二区三区| 久久精品国产AV一区二区三区| 狠狠色婷婷久久综合频道日韩 | av无码久久久久久不卡网站| 99久久精品国产麻豆| 国产69精品久久久久9999| 91精品国产高清久久久久久国产嫩草| 久久国产免费| 久久精品免费一区二区| 成人国内精品久久久久一区| 亚洲狠狠久久综合一区77777| 久久99精品久久久久久秒播 | 久久亚洲精品成人av无码网站| 久久精品亚洲中文字幕无码麻豆| 国产精品一区二区久久不卡| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 亚洲va国产va天堂va久久| 国产精品岛国久久久久| 久久精品三级视频| 色欲久久久天天天综合网| 久久精品国产亚洲网站| 国产精品99久久久久久宅男小说| 国产成人久久AV免费| 合区精品久久久中文字幕一区| 久久久久亚洲av无码专区导航| 97精品国产97久久久久久免费| 亚洲国产小视频精品久久久三级 | 浪潮AV色综合久久天堂| 久久人妻少妇嫩草AV无码蜜桃| 久久精品水蜜桃av综合天堂| 久久黄视频|