[HDU 1269] 미궁의 성

[HDU 1269] 미로성 강연통 템플릿은 전체 그림에 강연통 분량이 하나밖에 없으면 Yes 그렇지 않으면 No
좀 독립적인 점이 있을 수 있으니까 처음부터 끝까지 다 훑어보고 WA절도 몇 개를 드렸어요.
코드는 다음과 같다.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

vector <int> head[11111];
stack <int> s;
int dfn[11111],low[11111];
int vis[11111];
int f,t,n,m;

void Init()
{
    int i;
    for(i = 1; i <= n; ++i)
        head[i].clear();
    t = f = 0;
    memset(vis,0,sizeof(vis));
    while(!s.empty()) s.pop();
}

void Tarjan(int u)
{
    dfn[u] = low[u] = t++;
    int i,v;
    s.push(u);
    vis[u] = -1;
    for(i = 0; i < head[u].size(); ++i)
    {
        v = head[u][i];
        if(!vis[v])
        {
            Tarjan(v);
            if(f == 2) return;
            low[u] = min(low[v],low[u]);
        }
        else if(vis[v] == -1)
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(dfn[u] == low[u])
    {
        if(f)
        {
            f = 2;
            return;
        }
        f = 1;
        while(s.top() != u)
        {
            vis[s.top()] = 1;
            s.pop();
        }
        vis[s.top()] = 1;
        s.pop();
    }
}

int main()
{
    int i,u,v;
    while(~scanf("%d %d",&n,&m) && (m+n))
    {
        Init();
        for(i = 0; i < m; ++i)
        {
            scanf("%d %d",&u,&v);
            head[u].push_back(v);
        }
        for(i = 1; i <= n; ++i)
            if(!vis[i])
                Tarjan(i);
        if(f == 1) printf("Yes
");
        else printf("No
");
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU 1269] 미궁의 성

[HDU 1269] 미로성 강연통 템플릿은 전체 그림에 강연통 분량이 하나밖에 없으면 Yes 그렇지 않으면 No 좀 독립적인 점이 있을 수 있으니까 처음부터 끝까지 다 훑어보고 WA절도 몇 개를 드렸어요. 코드는 다...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[HDU 1269] 미궁의 성

좋은 웹페이지 즐겨찾기