Codeforces 243B Hydra

題目敘述：

給一個圖，沒有自環或重邊，問有沒有一隻多頭龍

有一個很簡單的作法可行：

『枚舉 u，然後枚舉 v，接著判斷可不可以』


也就是O(E)＊一個不知道是多少但感覺很大的東西


感覺就會TLE，但這題神奇的地方就在於他的時間複雜度

先把可以當成頭的點記錄起來，接下來判斷可以當成尾巴的點的數量

作法如下：

如果head的數量夠多，且某個head可以當成tail，那就把它當成tail

如果他只能是tail，照樣把它當成tail

一直做到有足夠的tail了或是沒辦法再有其他tail了，就結束

for(int i = 0; cnt < t && i < SZ(G[v]); i++)

{

    int x = G[v][i];

    if(x == u) continue;

    if(rem && vst[x]) rem--, tail[cnt++] = x;

    else if(!vst[x]) tail[cnt++] = x;

}

重點其實就是怕cnt不會變多（因為 t <= 100）

但如果cnt不會變多，其實也就是 rem == h

那麼最多跑 h 次，cnt便又會開始增加

因此時間複雜度為O(h+t)，總時間複雜度O(E*(h+t))，2*10^7

//By momo
#include<cstdio>
#include<vector>
#include<algorithm>

#define N 100010
#define PB push_back
#define SZ(x) (int)((x).size())
#define FOR(it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

int n, m, h, t;
int vst[N], rev[N], che[N];
vector<int> G[N];

int main(){
    scanf("%d%d%d%d", &n, &m, &h, &t);
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].PB(b); G[b].PB(a);
    }
   
    for(int u = 1; u <= n; u++)
    {
        if(SZ(G[u]) <= h) continue;
        FOR(it, G[u]) vst[*it] = 1;
        FOR(it, G[u])
        {
            if(SZ(G[*it]) <= t) continue;

            int v = *it;
            int cnt = 0;
            int rem = SZ(G[u])-h-1;

            for(int i = 0; cnt < t && i < SZ(G[v]); i++)
            {
                int x = G[v][i];
                if(x == u) continue;
                if(rem && vst[x]) rem--, che[x] = 1, rev[cnt++] = x;
                else if(!vst[x]) rev[cnt++] = x;
            }

            if(cnt == t)
            {
                printf("YES\n%d %d\n", u, v);
                int c = 0;
                FOR(it2, G[u])
                {
                    if(che[*it2] || *it2 == v) continue;
                    printf("%d ", *it2);
                    if((++c) == h) break;
                }puts("");
                for(int i = 0; i < cnt; i++) printf("%d ", rev[i]);
                puts("");

                return 0;
            }

            for(int i = 0; i < cnt; i++) che[rev[i]] = 0;
        }
        FOR(it, G[u]) vst[*it] = 0;
    }
    puts("NO");
}