HDU 1878図のオーラ戻り路の判断なし

4238 ワード

クリックしてリンクを開く

オーラかいろ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8198 Accepted Submission(s): 2933
Problem Description
オラ回路とは、ペンを紙面から離さず、図中の各エッジを1回だけ描くことができ、起点に戻ることができる回路のことです.今、オラ回路があるかどうかを尋ねる図を与えます.

Input
テスト入力には、いくつかのテスト例が含まれます.各試験例の1行目には、ノード数N(1束.

Output
各試験例の出力は1行を占め、オーラ戻り路が存在する場合は1を出力し、そうでない場合は0を出力する.

Sample Input

Sample Output

1
0

Author
ZJU

Source
浙大コンピュータ大学院生の再試験の上機試験-2008年

オーラかいろ
欧拉回路:図G、もし1本の道が存在するならば、Gの中を通る各辺は1回しかなくて、この道を欧拉路と呼んで、もし1本の回路が存在するならばGの各辺は1回しかなくて、
この回路をオラ回路と呼ぶ.オーラ戻り路を有する図がオーラ図となる.
オラロードが存在するかどうかを判断する方法
有向図:図連通、1つの頂点出度大入度1、1つの頂点入度大出度1があり、残りは出度=入度である.
無方向図:図は連通しており、2つの頂点だけが奇数度であり、残りは偶数度である.
オラ回路が存在するか否かを判断する方法
有向図:図連通、すべての頂点出度=入度.
無方向図:図が連通し、すべての頂点が偶数度です.

DFSでオーラの戻り道を判断する:

#include<stdio.h>
#include<vector>
using namespace std;
int deg[1007],vis[1007];
int n,m;
vector<int>v[1007];

void init()
{
    for(int i=1;i<=n;i++)
    {
        deg[i]=0;
        vis[i]=0;
        v[i].clear();
    }
}

void dfs(int point)
{
    vis[point]=1;
    for(int i=0;i<v[point].size();i++)
    {

        int next=v[point][i];
        //printf("%d
",next);
        if(!vis[next])
            dfs(next);
    }
}

int main()
{
    while(scanf("%d",&n),n)
    {
        scanf("%d",&m);
        init();
        int a,b;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            v[a].push_back(b);
            v[b].push_back(a);
            deg[a]++;
            deg[b]++;
        }
            int flag=1;
            for(int i=1;i<=n;i++)
                if(deg[i]%2)
                {
                    printf("0
");
                    flag=0;
                    break;
                }
            if(!flag)continue;
            dfs(1);
            for(int i=1;i<=n;i++)
                if(!vis[i])
                {
                    flag=0;
                    break;
                }
            if(flag)
                printf("1
");
            else
                printf("0
");
    }
    return 0;
}

ユーラシアの戻り道を判断するために、パラレルコレクションを使用します.

#include<stdio.h>
using namespace std;
int pre[1007],dge[1007];
int n,m;

void init()
{
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
        dge[i]=0;
    }
}

int find(int x)
{
    while(x!=pre[x])
        x=pre[x];
    return x;
}

void unio(int i,int j)
{
    /*int x=find(i);
    int y=find(j);
    if(x==y)return;
    pre[x]=y;*/
    pre[j]=find(i);
}

int main()
{
    while(scanf("%d",&n),n)
    {
        scanf("%d",&m);
        init();
        int a,b;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            dge[a]++;
            dge[b]++;
            if(find(a)!=find(b))
                unio(a,b);
        }
        int flag=0;
        for(int i=1;i<=n;i++)
            if(dge[i]%2)
            {
                printf("0
");
                flag=1;
                break;
            }
        if(flag)continue;
        int x=pre[1];
        for(int i=2;i<=n;i++)
            if(x!=find(i))
            {
                flag=1;
                break;
            }
        if(flag)
            printf("0
");
        else
            printf("1
");
    }
    return 0;
}

Java面接知識点(四十九)Map集合の遍歴

【Corda】RPCOpsのコマンドまとめ