CCF认证201512-4送货

原题链接

CCF认证201512-4送货

思路

判断是否存在欧拉回路

无向图:每个顶点的入度为偶数
有向图:每个顶点的入度和出度相等

判断是否存在欧拉路径、

无向图:源点和终点度数为奇数,其它点度数为偶数
有向图:一个顶点出度=入度+1,一个顶点 入度=出度+1,其他顶点 出度=入度

模板

递归方式

void dfs(int u){
    for(int v=1; v<=N; v++)
        if(G[u][v]){
            G[u][v]-=1;
            G[v][u]-=1;
            dfs(v);
        }
    ans.push(u);
} 

非递归方式
““cpp
stack s;
s.push(1);//化为非递归
while(!s.empty()){
int v = s.top(),i;
for(i=0;i<graph[v].size();++i){
int w = graph[v][i];
if(!visited[v][w]){
s.push(w);
visited[v][w] = true;
visited[w][v] = true;
break;
}
}
//不存在未访问过的点
if(i == graph[v].size()){
path.push_back(v);
s.pop();//出栈
}
}

#### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;

vector<int> graph[10010],path;//图和欧拉路径
int n,m;
bool visited[10010][10010];

bool f(vector<int>&v){//顶点v的度数是否为奇数
    return v.size()%2==1;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    //保证输入路径最小序 
    for(int i=1;i<=n;i++){
        sort(graph[i].begin(),graph[i].end());
    }
    stack<int> s;
    s.push(1);//化为非递归 
    while(!s.empty()){
        int v = s.top(),i;
        for(i=0;i<graph[v].size();++i){
            int w = graph[v][i];
            if(!visited[v][w]){
                s.push(w);
                visited[v][w] = true;
                visited[w][v] = true;
                break;
            }
        } 
        //不存在未访问过的点 
        if(i == graph[v].size()){
            path.push_back(v);
            s.pop();//出栈 
        }
    }
    int k=count_if(graph+1,graph+n+1,f);//度数为奇数的顶点个数
    if(path.size()==m+1&&(k==0||(k==2&&f(graph[1]))))
        for(auto i=path.rbegin();i!=path.rend();++i)//倒序输出
            printf("%d ",*i);
    else
        printf("-1");
    return 0;
}

Add a Comment

邮箱地址不会被公开。