44pt 求调
查看原帖
44pt 求调
735666
thinkerliu楼主2023/10/7 23:15

本地爆栈了。。。

#include <bits/stdc++.h>

class Edge
{
public:
    int to;
    int next;
};

Edge edges[500050 * 2];
int  heads[500050];
int  dfn[500050];
int  low[500050];
bool check[500050];
auto ans = 0;

auto cnt = 0;
void add(int u, int v)
{
    edges[++cnt].to = v;
    edges[cnt].next = heads[u];
    heads[u]        = cnt;
}

auto time_stamp = 0;
void tarjan(int now, int parent)
{
    dfn[now] = low[now] = ++time_stamp;
    
    auto child = 0;
    for (auto i = heads[now]; i; i = edges[i].next)
    {
        if (!dfn[edges[i].to])
        {
            tarjan(edges[i].to, now);

            low[now] = std::min(low[now], low[edges[i].to]);

            if (low[edges[i].to] >= dfn[now])
            {
                child++;
            }
        }
        else if (edges[i].to != parent)
        {
            low[now] = std::min(low[now], dfn[edges[i].to]);
        }
    }

    if ((now == parent && child >= 2) || (now != parent && child >= 1))
    {
        check[now] = true;
        ans++;
    }
}

int n, m, u, v;
int main()
{
    std::cin >> n >> m;
    for (auto i = 1; i <= m; i++)
    {
        std::cin >> u >> v;

        add(u, v);
        add(v, u);
    }

    for (auto i = 1; i <= n; i++)
    {
        if (!dfn[i])
        {
            tarjan(i, i);
        }
    }

    std::cout << ans << std::endl;
    for (auto i = 1; i <= n; i++)
    {
        if (check[i])
        {
            std::cout << i << std::endl;
        }
    }

    return 0;
}
2023/10/7 23:15
加载中...