낙곡월세SAC#1 - ACOJ 클라우드 평가 계획

제목 설명

ACOJ의 서버는 정말 끔찍한 지경에 이르렀다.그래서 SAC의 출제자인 SOL은 ACOJ 패키지를 다운로드하여 구축한 모든 지점을 주요 사이트에서 클라우드 평가 서비스를 시작하도록 강요해야 했다.클라우드 평가 서비스는 네트워크로 연결된다.이런 네트워크 연결은 양방향이다.그러나 지리적 위치 등의 제한으로 인해 임의의 두 서버가 직접 연결될 수 있는 것은 아니다.ACOJ 메인스테이션은 n개의 터미널(주역 포함)과 그들의 m개 연결 상황을 포함하여 직접 연결할 수 있는 서버의 표를 받았습니다. 이에 따라 각 터미널의 임무를 분배할 수 있습니다.일부 지점의 서버 주인은 SOL의 뇌장애자이다.그들은 무조건 그들의 서버를 SOL에 제공할 것이다.이 ACOJ 지점들을'좋은 역'이라고 부른다.하지만 일부 지점의 서버 주인은 SOL 블랙이다.그들은 ACOJ 서버를 얻었지만 SOL에 자원을 제공하기를 원하지 않아 흑기술을 이용하여 클라우드 서비스를 껐다.즉, 메인 사이트는 여전히 이 사이트들이 존재한다고 생각하지만, 통신을 전달할 수도 평가할 수도 없다.그것들을 나쁜 역이라고 부른다.천신만고의 조사를 통해 SOL은 ACOJ 클라우드 평가 시스템에 가장 많은 k개의 나쁜 사이트가 존재한다는 것을 확정했고 이 k개의 나쁜 사이트는 ACOJ의 클라우드 네트워크를 더 이상 연결시키지 않을 것 같다!대위기!그러나 SOL은 너무 지혜롭지 못해서 어느 k인지 확실하지 않다.그래서 그는 네가 그를 도와 임의의 그룹이 네트워크가 더 이상 연결되지 않을 수 있는 k개 사이트를 찾아서 예방을 강화할 수 있도록 도와달라고 부탁했다.

출력 형식 가져오기

형식 입력:

입력은 m+1 행을 포함합니다.첫 번째 줄의 세 번째 정수 n, m, k.다음 m줄은 줄마다 두 개의 정수 a, b로 표기된 a와 b의 사이트가 직접 연결될 수 있음을 나타낸다.

출력 형식:

출력은 한 줄을 포함합니다.k개의 정수를 초과하지 않고 원도를 잘라낼 수 있는 임의의 노드 조합을 나타낸다.Special Judge를 사용하기 때문에 노드의 순서는 걱정할 필요가 없습니다.원본을 잘라낼 수 있는 것만 만족시키면 된다.이러한 사이트 집합이 존재하지 않으면 "How oversuspicious you are, SOL!"을 출력합니다.만약 네트워크에 어떤 나쁜 사이트가 존재하지 않을 때 원래 연결할 수 없다면, "Poor SOL!"을 출력합니다.

내보내기 샘플 가져오기

샘플 입력 #1:

4 4 2
1 2
2 3
3 4
4 1

출력 샘플 #1:

1 3

샘플 입력 #2:

4 6 2
1 2
2 3
3 4
4 1
1 3
2 4

샘플 내보내기 #2:

How oversuspicious you are, SOL!

샘플 # 3 입력:

4 0 2

출력 샘플 #3:

Poor SOL!

문제를 보고 보니 np문제였는데 k<=3╮(╯╰)╭를 발견하고 대토론술을 하고 폭력을 휘두르자 233이 지났다.코드는 다음과 같습니다.

#include
#include
#include
#include
using namespace std;
const int sz = 60100;
int head[sz],nxt[sz],l[sz];
int dfn[501],low[501],dfs_clock;
bool is_cut[501];
int tot = 1,n,m,k;
bool use[501],vis[501];
void build_edge(int f,int t)
{
    l[tot] = t;
    nxt[tot] = head[f];
    head[f] = tot ++;
}
int tarjan(int u,int fa)
{
    int child = 0;
    dfn[u] = low[u] = ++ dfs_clock;
    for(int i = head[u] ; i ; i = nxt[i])
    {
        int v = l[i];
        if(!dfn[v] && !use[v])
        {
            child ++;
            low[v] = tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u])
                is_cut[u] = 1;
        }
        else if(v != fa && dfn[v] < low[u] && !use[v])
            low[u] = dfn[v];
    }
    if(fa == 0 && child == 1)
        is_cut[u] = 0;
    return low[u];
}
int read()
{
    int x = 0 , f = 1;
    char in = getchar();
    while(in < '0' || in > '9')
    {
        if(in == '-')
            f = -1;
        in = getchar();
    }
    while('0' <= in && in <= '9')
    {
        x = x * 10 + in - '0';
        in = getchar();
    }
    return x * f;
}
void init()
{
    dfs_clock = 0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(is_cut,0,sizeof(is_cut));

}
void dfs(int u)
{
    vis[u] = 1;
    for(int i = head[u] ; i ; i = nxt[i])
        if(!use[l[i]] && !vis[l[i]])
            dfs(l[i]);
    return ;
}
int main()
{
    n = read() , m = read() , k = read();
    for(int i = 1 ; i <= m ; i ++)
    {
        int f = read() , t = read();
        build_edge(f,t);
        build_edge(t,f);
    }
    {
        int ans = 0;
        for(int i = 1 ; i <= n ; i ++)
            if(!vis[i])
                dfs(i),ans ++;
        if(ans > 1)
        {
            puts("Poor SOL!");
            return 0;
        }
    }
    if(k == 1)
    {
        tarjan(1,0);
        for(int i = 1 ; i <= n ; i ++)
            if(is_cut[i])
            {
                printf("%d
",i);
                return 0;
            }
    }
    if(k == 2)
    {
        for(int i = 1 ; i <= n ; i ++)
        {
            init();
            use[i] = 1;
            for(int j = 1 ; j <= n ; j ++)
                if(!use[j])
                {
                    tarjan(j,0);
                    break;
                }
            use[i] = 0;
            for(int j = 1 ; j <= n ; j ++)
                if(j != i && is_cut[j])
                {
                    printf("%d %d
",i,j);
                    return 0;
                }
        }
    }
    if(k == 3)
    {
        for(int i = 1 ; i <= n ; i ++)
        {
            for(int j = i + 1 ; j <= n ; j ++)
            {
                init();
                use[i] = 1 , use[j] = 1;
                for(int k = 1 ; k <= n ; k ++)
                    if(!use[k])
                    {
                        tarjan(k,0);
                        break;
                    }
                use[i] = 0 , use[j] = 0;
                for(int k = 1 ; k <= n ; k ++)
                    if(k != i && k != j && is_cut[k])
                    {
                        printf("%d %d %d
",i,j,k);
                        return 0;
                    }
            }
        }
    }
    puts("How oversuspicious you are, SOL!");
    return 0;
}
/*
6 7 1
1 2
1 3
1 4
2 5
3 5
4 5
5 6
*/