yigun1029   2년 전

11퍼센트까지 채점되다 출력 초과라는데..

#include <bits/stdc++.h>
#define mp make_pair
#define sz(n) (int)n.size()

using namespace std;

pair <int, int> node[1234567];
stack <int> S;
vector <int> V[1234567], dap;

int visit[1234567];

int main()
{
    int i, v, e, nodenum=2, n = 0;

 //   freopen("input.txt", "r", stdin);

    scanf("%d%d", &v, &e);

    for (i=1; i<=e; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        V[a].push_back(b);
        V[b].push_back(a);
    }

    node[1] = mp(1, 1);
    S.push(1);

    while(S.size())
    {

        n = S.top();
        visit[n] = true;

        int check = 0;
        for(i=0; i<sz(V[n]); i++)
        {
            if(visit[ V[n][i] ] == false)
            {
                check++;
                node[ V[n][i] ] = mp(nodenum, nodenum);
                nodenum++;
                S.push(V[n][i]);
                break;
            }
        }

        if(check) continue; // 정상적인 노드

        if(check == 0) // 그냥 갈곳 없는애들
        {
            S.pop();
            if(S.empty()) break;
            int p = S.top();
            S.push(n);

            int qwer = node[n].first;
            int flg = 0;
            for(i=0; i<sz( V[n] ); i++)
            {
                if(V[n][i] != p && node[ V[n][i] ].first < qwer)
                {
                    flg = 10;
                    break;
                }
            }

            if(flg == 0)
            {
                S.pop();
                continue;
            }
        }

        if(check == 0) // 사이클여부 판단
        {
            S.pop();
            int p = S.top();
            S.push(n);

            for(i=0; i<sz(V[n]); i++)
            {
                if(V[n][i] != p)
                {
                    check++;
                    if(node[n].second > node[ V[n][i] ].first)
                        node[n] = mp(node[n].first, node[ V[n][i] ].first);
                }
            }
        }

        if(check == 0) // 맨끝노드
        {
            node[n] = mp(node[n].first, 0);
            S.pop();

            continue;
        }

        int q = node[n].second;
        S.pop();

        while (node[S.top()].first > q) // 사이클을 되돌아가면서 처리해줌
        {
            int ant = S.top();
            S.pop();

            node[ant] = mp(node[ant].first, q);
        }
    }

    for(i=1; i<=v; i++)
    {
        if(node[i].first <= node[i].second && V[i].size() != 1) dap.push_back(i);
    }

    printf("%d\n", sz(dap));

    for(i=0; i<sz(dap); i++) printf("%d ", dap[i]);

    return 0;
}

djm03178   2년 전

글을 올릴 때 카테고리를 질문으로 설정하면 문제 번호를 선택하는 칸도 있고 코드를 올리는 칸도 있습니다.

댓글을 작성하려면 로그인해야 합니다.