MENU

UOJ#67/JZOJ4679 新年的毒瘤/种树

UOJ#67

正解需要你理解什么叫做树。如果你对树的理解仅仅是“长得像树的家伙”就完蛋了。
我们需要用一个定义来规定什么叫做树。我们可以理解成,有 $n−1$ 条边的无向连通图。“有 $n−1$ 条边” 提示我们最终图里有 $n−2$ 条边,所以你需要删一个度数为 $m−(n−2)$ 的结点。
考虑第二个条件,也就是说删掉这个点后剩下的图仍然连通,所以这个点不是割点就行了。
所以用 Tarjan 算法求割点,然后输出所有不是割点且度数满足条件的结点就行了。可以获得 100 分。

Goodbye Jiawu 题解

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;
struct io {
    static const int L = (1 << 21) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
    void putc(char X) {
        *oS++ = X;
        if(oS == oT)flush();
    }
    char gc() { return iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, L, stdin), (iS == iT ? EOF : *iS++)) : *iS++; }
    template<class T>T rd() {
        int c = gc();
        T X = 0;
        for(; !isdigit(c); c = gc());
        for(; isdigit(c); c = gc())X = X * 10 + (c & 15);
        return X;
    }
    template<class T>void print(T X) {
        if(!X) { putc('0'); return; }
        int tp = 0;
        for(; X; st[tp++] = X % 10 + 48, X /= 10);
        for(tp--; ~tp; putc(st[tp--]));
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), m = ip.rd<int>(), dfn[100001], low[100001], idx, ans[100001], cnt;
bool flag[100001];
vector<int> e[100001];
inline void dfs(int u, int fa) {
    dfn[u] = low[u] = ++idx;
    int child = 0;
    for(int v : e[u]) {
        if(v == fa)continue;
        if(dfn[v])low[u] = min(low[u], dfn[v]);
        else {
            ++child, dfs(v, u), low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u])flag[u] = 1;
        }
    }
    if(u == 1 && child <= 1)flag[1] = 0;
}
int main() {
    int need = m - n + 2;
    while(m--) {
        int v = ip.rd<int>(), u = ip.rd<int>();
        e[v].push_back(u), e[u].push_back(v);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; ++i)if(!flag[i] && e[i].size() == need)ans[++cnt] = i;
    ip.print(cnt), ip.putc('\n');
    for(int i = 1; i <= cnt; ++i)ip.print(ans[i]), ip.putc(' ');
}