P3388 割顶【求割点个数】

输入格式

第一行输入两个正整数

下面

输出格式

第一行输出割点个数。

第二行按照节点编号从小到大输出节点，用空格隔开。

输入输出样例

输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

1 
5

CODE

    #include     <    bits/stdc++.h    >   
    #define     dbg    (    x    ) cout     << #x     <<     "    =    "     << x     << endl   

    using     namespace     std    ;   
    typedef     long     long LL    ;   
    const     int maxn     =     1e5     +     7    ;   

    int head    [maxn    ], dfn    [maxn    ], low    [maxn    ];   
    int cnt     =     0    , tot     =     0    , tim     =     0    , top     =     1    , cl     =     0    , k    ;   
    int vis    [maxn    ];   
    int color    [maxn    ];   
    int iscut    [maxn    ];   
    int tott    , n    , m    ;   

    /*   
    head[],结构体edge:存边   

    dfn[],low[]:tarjan中数组   

    st[]:模拟栈   

    out[]:出边   

    sd[]:强连通分量存储   

    dq[]:统计答案   
    */   

    template    <    class     T    >    inline     void     read    (    T     &    res    )   
    {   
            char c    ;T flag    =    1    ;   
            while    ((c    =    getchar    ())    <    '    0    '    ||c    >    '    9    '    )    if    (c    ==    '    -    '    )flag    =-    1    ;res    =c    -    '    0    '    ;   
            while    ((c    =    getchar    ())    >=    '    0    '    &&c    <=    '    9    '    )res    =res    *    10    +c    -    '    0    '    ;res    *=flag    ;   
    }   

    struct     Edge    {   
            int nxt    , to    ;   
    }    edge    [maxn     *     2    ];   

    inline     void     BuildGraph    (    int     from    ,     int     to    )   
    {   
        cnt    ++    ;   
        edge    [cnt    ].to     = to    ;   
        edge    [cnt    ].nxt     = head    [from    ];   
        head    [from    ]     = cnt    ;   
    }   

    stack    <int> s    ;   

    void     tarjan    (    int     u    ,     int     fa    )   
    {   
            int son     =     0    ;   
        s    .    push    (u    );   
        low    [u    ]     = dfn    [u    ]     =     ++tim    ;   
            for     (     int i     = head    [u    ]; i    ; i     = edge    [i    ].nxt     )     {   
                int v     =     edge    [i    ].    to    ;   
                if    (    !    dfn    [v    ])     {   
                    tarjan    (v    , fa    );   
                    low    [u    ]     =     min    (    low    [u    ],     low    [v    ]);   
                    if    (    low    [v    ]     >=     dfn    [u    ]     && u     != fa    )     {   
                        iscut    [u    ]     =     1    ;   
                    }   
                    if    (u     == fa    )     {   
                        ++son    ;   
                    }   
                }   
                low    [u    ]     =     min    (    low    [u    ],     dfn    [v    ]);   
            }   
            if    (son     >=     2     && u     == fa    )     {   
                iscut    [    1    ]     =     1    ;   
            }   
    }   

    void     init    ()     {   
        cnt     =     0    ;   
        cl     =     0    ;   
        tim     =     0    ;   
        k     =     0    ;   
            while    (    !s    .    empty    ())     {   
                s    .    pop    ();   
            }   
           
            memset    (vis    ,     0    ,     sizeof    (vis    ));   
            memset    (dfn    ,     0    ,     sizeof    (dfn    ));   
            memset    (low    ,     0    ,     sizeof    (low    ));   
            memset    (iscut    ,     0    ,     sizeof    (iscut    ));   
            memset    (edge    ,     0    ,     sizeof    (edge    ));   
            memset    (head    ,     0    ,     sizeof    (head    ));   
    }   

    int     main    ()    
    {   
            init    ();   
            scanf    (    "%d     %d    "    ,    &n    ,     &m    );   
            for     (     int i     =     1    ; i     <= m    ;     ++i     )     {   
                int x    , y    ;   
                scanf    (    "%d     %d    "    ,    &x    ,     &y    );   
                BuildGraph    (x    , y    );   
                BuildGraph    (y    , x    );   
               
            }   
            for     (     int i     =     1    ; i     <= n    ;     ++i     )     {   
                if    (    !    dfn    [i    ])     {   
                    tarjan    (i    , i    );   
                }   
            }   
            for     (     int i     =     1    ; i     <= n    ;     ++i     )     {   
                if    (    iscut    [i    ])     {   
                    ++tott    ;   
                }   
            }   
            printf    (    "%d    \n"    ,tott    );   
            for     (     int i     =     1    ; i     <= n    ;     ++i     )     {   
                if    (    iscut    [i    ])     {   
                    printf    (    "%d         "    ,i    );   
                }   
            }   
            return     0    ;   
    }   