POJ-2230-Watchcow-欧拉回路的路径输出+结构体

Watchcow

这道题的题意好理解，就是要从1出发，每条边都走两遍，最后再回到1；

但是，我一开始没有想到和欧拉回路有什么关系；

学了求欧拉的dfs（）后，试了一下发现和样例差不多；

感觉求回路，什么走两边可能都要用这样的dfs；

这道题还有一个注意点，就是不能直接开bool vis [10007][10007];

反正就是一直wa

于是就学了一种新方法；

利用struct+vector的组合；

//#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
using namespace std;

int n,m;
struct node{
    int to;
    bool vis;
    node(){}　　　　　　　　　　　　　　　　　　　　//就是这个，
    node(int to,bool vis):to(to),vis(vis){}
};

vector<node>G[10000+10];

void init(){
    for(int i=1;i<=n;i++)
        G[i].clear();

}

void euler (int u)
{
    for(int v = 0; v < G[u].size(); v++)
    {
        int tmp = G[u][v].to;
        if( !G[u][v].vis)
        {
            G[u][v].vis=1;
            euler(tmp);
        }
    }
    printf("%d
",u);
}

int main(){
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[v].push_back(node(u,false));　　　　　　//再用这个，应该节省了很多空间。
        G[u].push_back(node(v,false));　　　　　　
    }
    euler(1);
    return 0;
}