当前位置: 代码迷 >> 综合 >> poj-2230- Watchcow
  详细解决方案

poj-2230- Watchcow

热度:105   发布时间:2023-11-06 18:51:43.0

题意:

对于给出的每条边都要正向反向都走一遍,其实就是有向图的欧拉回路.用了pair类型方便标记每条走过的边,参照欧拉回路的模板就可以了。

ps:特别鸣谢jacknazi的指点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> P;
vector<P> g[10010];
int vis[1000010];
int n,m;
void dfs(int u){for(int i = 0; i < g[u].size(); i++){P v = g[u][i];if(!vis[v.second]){vis[v.second] = 1;dfs(v.first);}}printf("%d\n",u); 
}
int main(){int u,v;while(scanf("%d %d",&n,&m)!=EOF){int tot = 0;for(int i=1;i<=m;i++){scanf("%d %d",&u,&v);g[u].push_back({v,++tot});g[v].push_back({u,++tot});}memset(vis,0,sizeof(vis));dfs(1);}return 0;
}