为什么不会tle啊时间复杂度不是O(N^ 2)吗

B3609 [图论与代数结构 701] 强连通分量

wusihao1931 @ 2022-10-07 22:02:57

#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 400010;

int n, m;
int id[N];
bool st[N];
int scc_cnt;
vector<int> ans[N];
stack<int> stk;
bool in_stk[N];
int h[N], e[M], ne[M], idx;
int low[N], dfn[N], timestamp;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

void tarjan(int u)
{
    low[u] = dfn[u] = ++ timestamp;
    stk.push(u), in_stk[u] = true;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j]) 
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        int y;
        scc_cnt ++ ;

        do
        {
            y = stk.top();
            stk.pop();
            in_stk[y] = false;
            id[y] = scc_cnt;
            ans[scc_cnt].push_back(y);
        } while (y != u);
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    st[0] = true;
    cout << scc_cnt << endl;
    for (int i = 1; i <= n;  i ++ )
    {
        if (st[id[i]]) continue;
        st[id[i]] = true;
        sort(ans[id[i]].begin(), ans[id[i]].end());
        for (int j = 0; j < ans[id[i]].size(); j ++ )
            printf("%d ", ans[id[i]][j]);
        puts("");
    }

    return 0;
}

by lichengyun @ 2022-10-07 22:07:13

@wusihao1931 Tarjan是O(N+M),M<<N^2……


by wusihao1931 @ 2022-10-08 09:07:00

@lichengyun 大哥看这步,假如只有一个联通块,那么外层循环(O(n)) + sort(O(nlogn)) 不就是O(n ^ 2logn)吗??

for (int i = 1; i <= n;  i ++ )
    {
        if (st[id[i]]) continue;
        st[id[i]] = true;
        sort(ans[id[i]].begin(), ans[id[i]].end());
        for (int j = 0; j < ans[id[i]].size(); j ++ )
            printf("%d ", ans[id[i]][j]);
        puts("");
    }

by lichengyun @ 2022-10-11 21:35:41

@wusihao1931 时间复杂度是 \Theta(\Sigma deg_i \log deg_i)=\Theta(m\log m)


|