[ 問效率 ] TOJ - 143

jd3

為什麼用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;
}

Sylveon

DFS : O( E+V )
Union-Find 平均使用的話可以達到均攤O(1)，總共為O(E)

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