查看: 689|回復: 3

[解決] [ 問效率 ] TOJ - 143

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

    台南一中資訊社程式設計達人 - 2014

    發表於 2014-9-28 00:57:57 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 jd3 於 2014-9-28 20:02 編輯

    為什麼用union-find會比dfs下去分快?
    是我的常數太大嗎...


    TLE CODE
    [C++] 純文本查看 復制代碼
    #include<iostream>
    #include<cstdio>
    #include<vector>
    
    using namespace std;
    
    vector<int> list[100010];
    int color[100010];
    
    bool dfs(int node)
    {
        for(int i = 0 ; i < list[node].size() ; i++)
        {
            int next_node = list[node][i];
            if(color[next_node] == color[node])
                return false;
            else if(color[next_node] == -1)
            {
                color[next_node] = 1-color[node];
                if(dfs(next_node) == false)
                    return false;
            }
        }
        return true;
    }
    
    int main()
    {
        int n,m;
        int a,b;
        while(~scanf("%d%d",&n,&m))
        {
            for(int i = 0 ; i < n ; i++)
            {
                color[i] = -1;
                list[i].clear();
            }
            
            
            for(int i = 0 ; i < m ; i++)
            {
                scanf("%d%d",&a,&b);
                list[a].push_back(b);
                list[b].push_back(a);
            }
            
            bool yes = true;
            for(int i = 0 ; i < n ; i++)
            {
                if(color[i] == -1)
                {
                //    cout << "start : " << i << endl;
                    color[i] = 1;
                    if(!dfs(0))
                    {
                        yes = false;
                        break;
                    }
                }
            }
            
            if(yes)
                puts("YES");
            else
                puts("NO");
        }
        
        return 0;
    }






    點評

    這題也能用dfs解喔?  發表於 2014-9-28 09:38
    <這是個人簽名欄位>
    回復

    使用道具 檢舉

  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2014-9-28 10:32:46 | 顯示全部樓層
    DFS : O( E+V )
    Union-Find 平均使用的話可以達到均攤O(1),總共為O(E)

    但是Union-Find的常數 << DFS+遞迴的常數,光看code長度就可以看的出來

    點評

    jd3
    大概瞭解了,thanks~  發表於 2014-9-28 20:03
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表