首页 > 代码库 > uva-10054-欧拉回路

uva-10054-欧拉回路

题意:一个项链上面的每一个珠子有俩种颜色,前面一个珠子后面的颜色和后面珠子的前面颜色一样,有一天它断了,

一个人去搜集,问,搜集到的珠子能不能再次串成项链

原以为是链表,原来链表这组数据过不了.

7
1 2
2 3
3 4
4 1
3 5
5 6
6 3

感觉新爷给的这组数据.

AC时间350ms

#include<stdio.h>#include<iostream>#include<queue>#include<memory.h>using namespace std;const int N = 1000;const int MAXP = 55;void print(int g[MAXP][MAXP], int s){    for(int i = 1; i <= 50; i++)    {        if(g[s][i])        {            g[s][i]--;            g[i][s]--;            print(g, i);            cout << i << " " << s << endl;        }    }}int main(){    freopen("d:\\1.txt", "r", stdin);    string no = "some beads may be lost";    int t;    cin >> t;    int tt = 0;    while (t--)    {        tt++;        if(tt != 1)        {            cout << endl;        }        cout << "Case #" << tt << endl;        int n;        cin >> n;        int du[MAXP];        int g[MAXP][MAXP];        memset(du, 0, sizeof(du));        memset(g, 0, sizeof(g));        int s, e;        for(int i = 0; i < n; i++)        {            cin >> s >> e;            du[s]++;            du[e]++;            g[s][e]++;            g[e][s]++;        }        int ok = 0;        for(int i = 1; i <= 50; i++)        {            if(du[i] % 2)                ok = 1;        }        if(ok)            cout << no << endl;        else        {            for(int i = 1; i <= 50; i++)                print(g, i);        }    }    return 0;}

 

uva-10054-欧拉回路