OJ Board

Code: Select all

 AC 0.292 .... 

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<ctype.h>
#include<iostream>
using namespace std;
#define MAX1 50+5
int tc;
int n;
int x, y;
int map[MAX1][MAX1];
bool vis[MAX1];
int goin[MAX1];
int cnt, node;
int stack[2000][2];
int top;
bool flag;

void dfs(int u)         //look for liangtong
{
    vis[u]=true;
    cnt++;
    if (cnt==node) {flag=true; return; }
    for (int v=1;v<=50;v++) if (map[u][v] && !vis[v])
    {
        dfs(v);
        if (flag) return;
    }
}

void euler(int u)
{
    if (top==n && stack[top][1]!=stack[1][0])           //mo wei bu tong jiu tui chu
    {
        return;
    }
    else if (top==n && stack[top][1]==stack[1][0])      //ruguo chengli jiu shezhi biaozhi bianliang flag
    {
        flag=true;
        return;
    }
    for (int v=1;v<=50;v++) if (map[u][v])
    {
        top++;
        stack[top][0]=u; stack[top][1]=v;
        map[u][v]--; map[v][u]--;
        euler(v);
        if (flag) return;                               //look for
        map[u][v]++; map[v][u]++;
        top--;
    }
}

void work()
{
    for (int i=1;i<=50;i++) if (goin[i]%2 != 0)
    {
        cout<<"some beads may be lost"<<endl;
        return;
    }
    cnt=0;
    flag=false;
    dfs(x);
    if (cnt < node)
    {
        cout<<"some beads may be lost"<<endl;
        return;
    }
    top=0;
    flag=false;
    euler(x);
    for (int i=1;i<=n;i++) cout<<stack[i][0]<<' '<<stack[i][1]<<endl;
}

int main()
{
    freopen("10054.in","r",stdin);
    freopen("10054.out","w",stdout);
    cin>>tc;
    for (int ii=1;ii<=tc;ii++)    
    {
        cin>>n;
        memset(map,0,sizeof(map));
        memset(vis,false,sizeof(vis));
        memset(goin,0,sizeof(goin));
        node=0;
        for (int i=1;i<=n;i++)
        {
            cin>>x>>y;
            map[x][y]++; map[y][x]++;
            if (!goin[x]) node++;
            goin[x]++;          //look for
            if (!goin[y]) node++;
            goin[y]++;
        }
        printf("Case #%d\n",ii);
        work();
        if (ii<tc) cout<<endl;
    }
    return 0;
}

Code: Select all

#include <stdio.h>
#define NUM 51
int v[NUM][NUM];

void eulercycle(int x){
    int i;
    for( i=1; i<NUM; i++){
        if(v[x][i]!=0){
           
            --v[x][i];
            --v[i][x];
            printf("%d %d\n", x, i);
            eulercycle(i);
        }
    }
}
int main(){
    int casenum, n, degree[NUM], i, j, k, c1, c2;
    int iseuler;
    scanf("%d", &casenum);
    for( i=1; i<=casenum; ++i){
        scanf("%d", &n);
        iseuler=1;
        
        for( j=0; j<NUM; ++j) degree[j]=0;
        for( j=0; j<NUM; ++j)
            for( k=0; k<NUM; ++k) v[j][k]=0;

        for( j=0; j<n; ++j){
            scanf("%d %d", &c1, &c2);
            
            ++v[c1][c2];
            ++v[c2][c1];
            ++degree[c1];
            ++degree[c2];
        }
        printf("Case #%d\n", i);
        
        for( j=1; j<NUM; ++j){
            if( degree[j]%2!=0){
                iseuler=0;
                break;
            }
        }

        if(iseuler){
            eulercycle(c1);
        }
        else{
            printf("some beads may be lost\n");
        }
    }
    return 0;
}

Code: Select all

2
3
1 2
2 2
2 1
3
2 2
2 1
1 2

Code: Select all

1
5
1 2
2 2
2 2
2 1
1 1

Code: Select all

list<int> edges[SIZE];
list<int> beads;

void tour(int node)
{
	stack<int> nodesToBeVisited;
	nodesToBeVisited.push(node);
	
	while(!nodesToBeVisited.empty())
	{
		node = nodesToBeVisited.top();
		nodesToBeVisited.pop();
		while(!edges[node].empty())
		{
			int nextNode = *edges[node].begin();
			beads.push_back(nextNode);
			edges[node].erase(edges[node].begin());
			edges[nextNode].erase(find(edges[nextNode].begin(), edges[nextNode].end(), node));
			nodesToBeVisited.push(nextNode);
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	
	int i, j, k, l, sum = 0;
	int tc, t, d, x, y, a, b, r, n, current, first;
	char ch;
	int mx;
	bool flag;
	unsigned long long ln;
	
	scanf("%d", &tc);
	
	for(t = 1; t <= tc; t++)
	{
		scanf("%d", &n);
		printf("Case #%d\n", t);
		
		for(i = 1; i <= 50; i++)
			edges[i].clear();
		beads.clear();
		
		for(i = 1; i <= n; i++)
		{
			scanf("%d %d", &x, &y);			
			edges[x].push_back(y);
			edges[y].push_back(x);
		}		
		
		flag = false;
		for(i = 1; i <= 50; i++)
			if(edges[i].size() % 2) {flag = true; break;}
		if(!flag)
		{
			beads.push_back(y);
			tour(y);
			
			if(beads.size() == n + 1)
			{
				list<int>::iterator it = beads.begin();
				while(true)
				{
					x = *it++;
					if(it != beads.end())
					{
						y = *it;
						printf("%d %d\n", x, y);
					}
					else break;
				}
			}
			else printf("some beads may be lost\n");
		}		
		else printf("some beads may be lost\n");
		
		if(t != tc) cout << endl;
	}
		
	return 0;
}

Code: Select all

#include <iostream>
#include <list>
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const int GRAPH_SIZE = 50;
int graph[GRAPH_SIZE][GRAPH_SIZE];
int n, x, y;
bool connected;
list<int> path;

void print_path() {
	int printFlag = 0;
	while(!path.empty()){
		int front = path.front();
		if (printFlag == 0) {
			cout << front << ' ';
			printFlag++;
		}
		else if (printFlag == 1) {
			cout << front << endl;
			printFlag = 0;
		}
		path.pop_front();
	}
}

void find_cycle(int pos, list<int>::iterator iter){

	for(int i = 0; i < GRAPH_SIZE; i++){
		if(graph[pos][i] > 0){
			graph[pos][i]--;
			graph[i][pos]--;
			iter = path.insert(iter, pos+1);
			iter = path.insert(iter, i+1);
			find_cycle(i, iter);
			break;
		}
	}

}

void reset() {
	for(int i = 0; i < GRAPH_SIZE; i++){
		for(int j = 0; j < GRAPH_SIZE; j++){
			graph[i][j] = 0;
		}
	}
}

bool edgesLeft() {
	int count = 0;
	for(int i = 0; i < GRAPH_SIZE; i++){
		for(int j = 0; j < GRAPH_SIZE; j++){
			count += graph[i][j];
		}
	}
	if (count > 0) {
		return true;
	}
	else {
		return false;
	}
}


int findNextEdge() {
	for(int i = 0; i < GRAPH_SIZE; i++){
		for(int j = 0; j < GRAPH_SIZE; j++){
			if (graph[i][j] > 0) {
				return i;
			}
		}
	}
	return -1;
}

void euler() {
	find_cycle(0, path.begin());
	while (edgesLeft()) {
		int edge = findNextEdge();
		list<int>::iterator iter = std::find(path.begin(), path.end(), edge+1);
		if (iter == path.end() && !path.empty() && path.back() != edge+1) {
			connected = false;
			return;
		}
		if (path.empty()) {
			find_cycle(edge, path.begin());
		}
		else {
			find_cycle(edge, ++iter);
		}
	}
}

int main(){

	int n, numBeads;
	cin >> n;
	for (int i=0; i < n; i++) {
		cout << "Case #" << i + 1 << endl;
		cin >> numBeads;
		for (int j = 0; j < numBeads; j++) {
			cin >> x >> y;
			graph[x-1][y-1]++;
			graph[y-1][x-1]++;
		}

		bool lostBeads = false;
		connected = true;
		//Check for not enough beads
		for (int j=0; j < GRAPH_SIZE; j++) {
			int vertexDegree = 0;
			for (int k=0; k < GRAPH_SIZE; k++) {
				if (graph[j][k] > 0) {
					vertexDegree += graph[j][k];
				}
				//cout << "[" << graph[j][k] << "] ";
			}
			if (vertexDegree % 2 != 0) {
				cout << "some beads may be lost" << endl;
				lostBeads = true;
				break;
			}
			//cout << endl;
		}
		if (!lostBeads) {
			euler();
			if (connected) {
				print_path();
			}
			else {
				cout << "some beads may be lost" << endl;
			}
		}
		reset();
		if (!(i == n-1)) {
			cout << endl;
		}
	}

}

Code: Select all

1
55
1 40
20 15
27 16
1 22
28 24
6 49
16 9
14 10
46 25
40 12
25 37
40 24
36 1
18 24
20 5
9 12
24 35
10 19
46 15
23 8
16 20
18 1
12 32
44 30
9 35
19 24
16 12
22 27
40 23
1 20
15 1
31 22
40 47
44 40
30 46
18 10
32 37
30 25
37 40
1 7
31 22
27 27
8 27
18 1
46 6
40 24
40 37
47 5
10 8
9 49
27 15
40 14
36 25
7 30
8 28

Code: Select all

Case #1
49 9
9 35
35 24
24 40
40 37
37 40
40 24
24 19
19 10
10 18
18 24
24 28
28 8
8 23
23 40
40 44
44 30
30 46
46 25
25 37
37 32
32 12
12 16
16 27
27 27
27 15
15 20
20 16
16 9
9 12
12 40
40 14
14 10
10 8
8 27
27 22
22 31
31 22
22 1
1 40
40 47
47 5
5 20
20 1
1 18
18 1
1 36
36 25
25 30
30 7
7 1
1 15
15 46
46 6
6 49