Codeforces Round #369 (Div. 2) D. Directed Roads 图论、组合学、二重dfs、并查集形式的图、Interesting、好题

Source

Codeforces Round #369 (Div. 2)

My Solution

图论、组合学、 二重dfs、并查集形式的图、Interesting、好题

可以把图分成两部分， 一部分是链状的 方案数是 2^k次(k条边)， 另一部分是很多的环((C m, 1) + (C m, 2) + (C m, 3) + ...... + (C m, m - 1) == 2^m - 1 - (C m, m) == 2^m - 2)

并查集形式的图, 一个节点自由一个父节点， 可能有环 father[ i ] = ai;

每个i， dfs， 访问到这个i访问过的节点是， 说明 有环， 然后进行 indfs 处理换， 并记录好在环中的边的个数 cntall

且用 flag 的布尔数组标记， 用来每个节点只访问一次， 遍历 i 时 if(flag[ i ]) continue;

在dfs内部， 访问一个节点就flag[ i (或 father[ u ] )] =  true;

虽然看上去已经用flag数组把O(n^2)优化到 O(n)了

但 Time limit exceeded on test 14

有特殊的情况没有处理 比如 1 < - 2 < - 3 < - 4 这样的图， 其实只要遍历一次就好

但按照如上的方法第一次 是访问1， 第二次访问1、2， 第三次 访问 1、2、3， 第四次访问 1、2、3、4， 所以有 以前遍历了这条链的一部分，然后大量的重复访问

这样最坏的复杂度 n*n/2 有O(n^2)了，

所以再加个标记数组cycle用来标记当前i， 访问过的节点用来处理圆， 每次回溯的时候重置好， 然后flag数组标记所有情况访问的节点

//此外做过这个题发现， 如果用STL_set， 每个i， clear然后用来标记， 比用布尔标记数组慢很多很多，所以如果条件允许则优先使用布尔数组来标记吧 Y ( ^ _  ^ ) Y

复杂度 O(n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2*1e5 + 8;
const LL Hash = 1e9 + 7;

LL father[maxn], pow2[maxn], cntall, ans;
//set s;
bool flag[maxn], cycle[maxn];  // cycle 用来单次的记录访问过点， 用来找出环

inline LL mod(LL x)
{
    return x - x / Hash * Hash;
}

inline void indfs(LL u, LL v, LL cnt)
{
    if(father[u] == u) return;
    if(father[u] == v){
        cntall += cnt;
        ans = mod(ans * (pow2[cnt] - 2));
        father[u] = u;
        return;
    }

    indfs(father[u], v, cnt + 1);

}

inline void dfs(LL u)
{
    if(father[u] == u) return;
    if(cycle[father[u]]){
        indfs(father[u], father[u], 1);
        return;
    }
    if(flag[father[u]]) return;
    //cout << u << " " << father[u] << endl;
    flag[father[u]] = true;
    cycle[father[u]] = true;
    //s.insert(father[u]);
    dfs(father[u]);
    cycle[father[u]] = false;

}


int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    memset(flag, false, sizeof flag);
    memset(cycle, false, sizeof flag);
    pow2[0] = 1;
    for(LL i = 1; i < maxn; i++){ pow2[i] = mod(pow2[i - 1] * 2ll); } int n; cin >> n;
    for(int i = 1; i <= n; i++){ cin >> father[i];
    }
    ans = 1, cntall = 0;
    for(int i = 1; i <= n; i++){
        if(flag[i]) continue;
        flag[i] = true;
        cycle[i] = true;
        //s.clear();
        //s.insert(i);
        dfs(i);
        cycle[i] = false;
    }

    ans = mod(ans * pow2[n - cntall]);
    //cout << cntall << endl;
    cout << mod(ans + Hash) << endl;

    #ifdef LOCAL
    cout<<endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx