[TIOJ] 1256 砲打皮皮4

LINK：http://tioj.infor.org/problems/1256
　　每次看到別人的code收藏區的咚咚，都會覺得別人怎麼那麼厲害已經學到了這麼多東西了，自己卻只能現在看著他的code來學習而覺得別人很厲害，所以我決定我這次不先說圖的關節點是我今天才在演算法筆記學到了，來自我感覺良好一下XD(我到底在說甚麼啊@@)
　　反正看到題目就知道是裸的圖的關節點了，刻一刻就好~~
　　對不起，現在想想，剛剛寫得太簡略了@@
　　總之先建一顆DFS樹，然後再分成tree edge和back edge來討論，若是back edge無法走到更高的點的話，也就是說某個點的子樹經由任何路徑最高只能走到那個子樹的第一個父親的話，那麼那顆父親就是關節點啦啦啦~~

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define getchar getchar_unlocked
#define putchar putchar_unlocked

inline void output(int _x)
{
    char _buff[20]; int _f = 0;
    while(_x > 0)
    {
        _buff[_f++] = _x%10+'0';
        _x /= 10;
    }
    for(_f-=1; _f >= 0; _f--)
        putchar(_buff[_f]);
    putchar(' ');
}

inline bool input(int &_x)
{
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-' && _tc != EOF) _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
    return _x;
}

int n,m,t,a,b,cnt;
vector<int> hand[10009];
int ans[10009];
int visit[10009];
int low[10009];
inline void dfs(int i,int p)
{
    int child = 0;
    bool ap = 0;
    visit[i] = low[i] = ++t;
    for(auto j:hand[i])
    {
        if(j == p) continue;
        if(visit[j]) low[i] = min(low[i],visit[j]);
        else
        {
            child++;
            dfs(j,i);
            low[i] = min(low[i],low[j]);
            ap =(low[j] >= visit[i]);
        }
    }
    if((i == p && child > 1) || (i != p && ap)) 
        ans[cnt++] = i;
}
int main()
{
    int tt = 0;
    while(input(n) && input(m))
    {
        memset(visit,0,sizeof(visit));
        t = cnt = 0; 
        for(int i = 1; i <= n; i++) hand[i].clear();
        while(m--)
        {
            input(a); input(b);
            hand[a].push_back(b);
            hand[b].push_back(a);   
        }
        dfs(1,1);
        printf("Case #%d:%d ",++tt,cnt);
        if(cnt == 0)
        {
            putchar('0');
            putchar('\n');
        }
        else
        {
            sort(ans,ans+cnt);
            for(int i = 0; i < cnt; i++)  output(ans[i]);
            putchar('\n');
        }
    }
}