萌新发问(求求了):用的邻接表加dfs,为什么会TLE啊?
查看原帖
萌新发问(求求了):用的邻接表加dfs,为什么会TLE啊?
497099
theshyer楼主2021/9/15 12:25
#include<bits/stdc++.h>

using namespace std;
int h[100010], e[100010], ne[100010], idx;

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

int dfn[100010], low[100010], tim;
bool vis[100010];

void dfs(int a, int fa)
{
    int child = 0;
    low[a] = dfn[a] = ++tim;
    for (int i = h[a]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            dfs(j, fa);
            low[a] = min(low[a], low[j]);
            if (a == fa)child ++;
            if  (a != fa && low[j] >= dfn[a]) 
                vis[a] = true;
        }
        else 
            low[a] = min(low[a], dfn[j]);
    }
    if (child >= 2 && a == fa)vis[a] = true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    } 
    for (int i = 1; i <= n; i++)
        if (!dfn[i])dfs(i, i);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (vis[i])cnt ++;
    cout << cnt << endl;
    for (int i = 1; i <= n; i++)
        if (vis[i])printf("%d ", i);
    return 0;
}
2021/9/15 12:25
加载中...