Algoogle

Algorithm for Programming Contest

PKU 2230 Watchcow

Category: PKU Tag: dfs

Watchcow

問題概要


M個の辺が与えられるのでそれら全ての辺を必ず往路と復路1回ずつ通るようにするときの経路.
ただし始点と終点は1

解法


DFSで行けるところまで潜っていく.
ただし一度使った辺は使わない.(往路のみ使う)
あとは各ノードでDFSするときに次のノードを出力, DFSから帰ってきた時に現在のノードを出力すれば復路を表現できる.
辺は多重に張られることもあるので注意.

コード


(2230.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

typedef pair<int,int> pii;

int N, M;
vector<pii> edge[10010];
bool used[50010];

void dfs(int p){
    for(int i = 0; i < edge[p].size(); i++){
        int nxt = edge[p][i].first, id = edge[p][i].second;
        if(used[id]) continue;
        used[id] = 1;
        printf("%d\n", nxt+1);
        dfs(nxt);
        printf("%d\n", p+1);
    }
}

int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; i++){
        int a, b; scanf("%d%d", &a, &b);
        a--; b--;
        edge[a].push_back(pii(b,i));
        edge[b].push_back(pii(a,i));
    }

    printf("1\n");
    dfs(0);
    return 0;
}

Comments