首页 > 其他分享 >poj 2230

poj 2230

时间:2023-02-19 14:12:35浏览次数:40  
标签:int 2230 dfs vis poj go include hd

求一个无向图的欧拉回路,但要求每条边正反过一次

 

当作有向图,打标记只打一条边

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std ;
  const int N= 1e5+3,M=N;
  
 stack<int> st;
 int all,nxt[M],go[N],hd[N];
 int n,m,vis[N];
 
 void add_(int x,int y){
	nxt[++all]=hd[x]; hd[x]=all;
	go[all]=y;
 }
 void dfs(int x){
 	for(int i=hd[x];i;i=nxt[i]){
 		int y=go[i];
 		if(vis[i]==0) vis[i]=1,dfs(y),st.push(x);
 	}
 }
 signed main(){
 	int i,a,b;
 	while(cin>>n>>m){
 		for(i=1;i<=n;i++) hd[i]=0; all=0;
 		while(st.empty()==0) st.pop();
 		
	 	for(i=1;i<=m;i++){
	 		cin>>a>>b;
	 		add_(a,b);add_(b,a);
	 	}
	 	dfs(1);
	 	while(st.empty()==0){
	 		cout<< st.top() <<endl; st.pop();
	 	}
	 	cout<<1<<endl;
 	}
 }

 

标签:int,2230,dfs,vis,poj,go,include,hd
From: https://www.cnblogs.com/towboa/p/17134670.html

相关文章

  • POJ - 1664 放苹果
    把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1是同一种分法。Input第一行是测试数据的数目t(0<=t<=20)。以下每行均包......
  • 二分查找水题--疯牛(POJ 2456)
    DescriptionFarmerJohnhasbuiltanewlongbarn,withN(2<=N<=100,000)stalls.Thestallsarelocatedalongastraightlineatpositionsx1,...,xN(0<=x......
  • Poj 2503 map sscanf
    Poj2503mapsscanf题意字符串的映射,但它输入的方式很怪。首先每行输入两个单词,中间隔一个空格,到输入空行为止。然后每行输入一个单词,如果能存在映射的单词就输出对......
  • Pseudoprime numbers(POJ-3641 快速幂)
    快速幂:快速幂就是所求的幂次方过大,导致代码所用的时间超限。如:求2^3,3的二进制是11,(n&1)判断次方数的二进制是否为1,n>>1,向右进位1:代码:k=1,t=n;while(n){if(n&1)//......
  • Cash Machine (POJ 1276)(多重背包——二进制优化)
    链接:POJ-1276题意:给你一个最大金额m,现在有n种类型的纸票,这些纸票的个数各不相同,问能够用这些纸票再不超过m的前提下凑成最大的金额是多少?题解:写了01背包直接暴力,结......
  • Subsequence (POJ - 3061)(尺取思想)
    ProblemAsequenceofNpositiveintegers(10<N<100000),eachofthemlessthanorequal10000,andapositiveintegerS(S<100000000)aregiven.W......
  • Til the Cows Come Home ( POJ 2387) (简单最短路 Dijkstra)
    problemBessieisoutinthefieldandwantstogetbacktothebarntogetasmuchsleepaspossiblebeforeFarmerJohnwakesherforthemorningmilking.......
  • POJ--2456 Aggressive cows(二分搜索/最大化最小值)
    记录22:552023-2-9http://poj.org/problem?id=2456reference:《挑战程序设计竞赛(第2版)》3.1.3p142DescriptionFarmerJohnhasbuiltanewlongbarn,withN(2......
  • POJ--3669 Meteor Shower(bfs/稍微变通)
    记录21:372023-2-9http://poj.org/problem?id=reference:《挑战程序设计竞赛(第2版)》第二章练习题索引p135DescriptionBessiehearsthatanextraordinarymeteor......
  • 【代码源 Div1 - 106】#456. 选数(抽屉原理) POJ2356
    problemsolution原本以为是01背包,但只能求出是否有解,没法求解对原数组求取模后的前缀和sum,则对于sum数组中的每个数,均位于[0,n-1],共n种取值,而sum[0~n]有n+1个......