CCF 201512-4 delivery

subject

Problem description

　　 In order to increase the company's revenue ,F The company has opened a new logistics business . because F The company has a good reputation in the industry , As soon as the logistics business was opened, it was welcomed by consumers , Logistics business immediately spread to every street in the city . However ,F The company now only arranges Xiaoming to be responsible for all street services .
　　 Although the task is arduous , But Xiao Ming has enough confidence , He got a map of the city , Prepare to study the best solution . There are... In the city n It's an intersection ,m The streets connect between these intersections , Every street is connected with an intersection at the beginning and end . Except at the beginning and end of the street , Streets do not intersect with other streets at other locations . Every intersection is connected to at least one street , Some intersections may only connect one or two streets .
　　 Xiao Ming wants to design a scheme , From the number 1 Starting at the intersection of , Every time you have to go along the street to the intersection at the other end of the street , Then start from the new intersection to the next intersection , Until all the streets passed just once .

Input format

　　 The first line of input contains two integers n, m, Indicates the number of intersections and the number of streets , Intersection from 1 To n label .
　　 Next m That's ok , Two integers per line a, b, The symbol and label are a The intersection and label of are b There is a street between the intersections of , The street is two-way , Xiao Ming can go from one end to the other . There is at most one street between two intersections .

Output format

　　 If Xiao Ming could pass every street just once , The output line contains m+1 It's an integer p1, p2, p3, ..., pm+1, It means the sequence of the intersections Xiao Ming passes , Two adjacent integers are separated by a space . If there are multiple schemes that meet the conditions , Then the output dictionary order is the smallest , That is, first of all, to ensure that p1 Minimum ,p1 To guarantee the minimum p2 Minimum , And so on .
　　 If there is no plan to make Xiao Ming pass each street just once , Then an integer is output -1.

The sample input

4 5
1 2
1 3
1 4
2 4
3 4

Sample output

1 2 4 1 3 4

Sample explanation

　　 The map of the city and Xiao Ming's path are shown in the following figure .

The sample input

4 6
1 2
1 3
1 4
2 4
3 4
2 3

Sample output

-1

Sample explanation

　　 The map of the city is shown in the figure below , There is no path that satisfies the condition .

Evaluate use case size and conventions

　　 front 30% The evaluation use case of meets ：1 ≤ n ≤ 10, n-1 ≤ m ≤ 20.
　　 front 50% The evaluation use case of meets ：1 ≤ n ≤ 100, n-1 ≤ m ≤ 10000.
　　 All evaluation cases meet ：1 ≤ n ≤ 10000,n-1 ≤ m ≤ 100000.

---

Topic analysis

Anyone who has studied graph theory should know that this problem is about Euler path , The sufficient and necessary condition for the existence of Euler path is ： All vertices have even degrees , Or only exist 2 The degree of points is odd （ this 2 Points are the starting and ending points of Euler's path ）. Of course , The main premise is to figure connected , Don't forget that .

First, judge whether the graph is connected , Use Union checking set , Simple and crude , My joint search set here adopts Path compression also Sum by size , The aim is to improve efficiency . Those who don't know and search the set can go to know first , A simple and powerful data structure .

After judging whether the graph is connected, we need to further judge whether there is an Euler path . We according to the Adjacency list （ The storage structure of the graph ） To calculate the degree of each vertex , The number of vertices with odd statistical degree , Then judge according to the conditions for the existence of Euler path .

Some of the subtleties of this algorithm are DFS Finally, use the stack to store the path . It is worth mentioning that , This question is DFS yes For edge Instead of targeting points .

Finally, I had to roast CCF Certified question bank OJ, First of all, even if there are spaces at the end of this question, it doesn't affect , But who dares not to deal with the tail space when the score is not displayed in the exam = =. More pit is , This problem has been changed 1 For hours 80 branch （ Running error ）, Then if you really can't find the error, copy others' submissions , As a result, all the answers found were copied （ Including giving screenshots 100 Points of ） Submit it all 80 branch （ Running error ）.●﹏●. It seems so CCF There is something wrong with the problem determination system of this problem ~~~~~

Code

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int MAX_V = 10000;

// Union checking set  
int p[MAX_V+1];

int Find(int x){
	if(p[x]>0)
		return p[x] = Find(p[x]);// Path compression  
	else
		return x;
}

void Union(int x,int y){
	int xroot = Find(x), yroot = Find(y);
	if(xroot!=yroot){
		// Operate by size  
		if(p[xroot] <= p[yroot]){// With xroot The tree with roots is bigger 
			p[xroot] += p[yroot];
			p[yroot] = xroot;
		}
		else{// With yroot The tree with roots is bigger  
			p[yroot] += p[xroot];
			p[xroot] = yroot;
		}
	}
}
// Union checking set -end

bool visited[MAX_V+1][MAX_V+1] = {false};

void dfs(const vector<vector<int> > &Vertexs,const int &V,stack<int> &path){
	for(vector<int>::const_iterator it = Vertexs[V].begin();it != Vertexs[V].end();it++){
		if(!visited[V][*it]){
			visited[V][*it] = visited[*it][V] = true;
			dfs(Vertexs,*it,path);
		}
	}
	path.push(V);
}

int main(){
	int n,m,t1,t2;
	scanf("%d %d",&n,&m);
	vector<vector<int> > Vertexs(n+1);//0 Unit No. is vacant  
	stack<int> path;
	
	for(int i=1;i<=n;i++)// Initialize and query set  
		p[i] = -1;//p[root] Record to root Is the opposite number of nodes in the root tree , To distinguish between roots and ordinary nodes  
	
	for(int i=0;i<m;i++){
		scanf("%d %d",&t1,&t2);
		if(!visited[t1][t2]){
			Vertexs[t1].push_back(t2);
			Vertexs[t2].push_back(t1);
			Union(t1,t2);
		}
	}
	
	// Check connectivity  
	t1 = Find(1);
	for(int i=2;i<=n;i++){
		if(Find(i)!=t1){// Disconnected  
			printf("-1\n");
			return 0;
		}
	}
	
	// Check whether there is Euler path ： All vertices have even degrees   or   There is only 2 vertices （ Start and end ） Degree is odd  
	int cnt = 0;
	for(int i=1;i<=n;i++){
		if(Vertexs[i].size() % 2 != 0)
			cnt++;
	}
	if(!(cnt==0 || (cnt==2 && Vertexs[1].size() % 2 != 0))){// There is no Euler path  
		printf("-1\n");
		return 0;
	}
	
	// There is an Euler path  
	for(int i=1;i<=n;i++)// Sort each adjacency table , Ensure that the path is selected in dictionary order under multiple solutions  
		sort(Vertexs[i].begin(),Vertexs[i].end());
	
	dfs(Vertexs,1,path);
	
	while(!path.empty()){
		t1 = path.top();
		path.pop();
		printf("%d ",t1);
	}
	printf("\n");
	
	return 0;
}