uva 10054 The Necklace

제목 주소:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=995
이 문제의 제목은 T조 데이터, n개 변, 각 변은 두 개의 점을 연결하고 오로라 회로를 형성할 수 있느냐는 것이다.
두 번째 데이터에서 이 문제는 무방향도임을 알 수 있다.
AC 코드
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int map[60][60];
int vis[60];
int num[60];
int counts,n,b;
void dfs(int d)
{
    vis[d]=1;
    counts++;
    for(int i=0;i<=b;i++)
    {
        if(map[d][i]&&!vis[i])
        {
            dfs(i);
        }
    }
    return ;
}
void euler(int a)
{
    for(int i=1;i<=b;i++)
    {
        if(map[a][i])
        {
            map[a][i]--;
            map[i][a]--;
            euler(i);
            printf("%d %d
",i,a); } } return; } int main() { int ncase,x,y,colorcont; scanf("%d",&ncase); for(int k=0;k<ncase;k++) { if(k) printf("
"); memset(vis,0,sizeof(vis)); memset(map,0,sizeof(map)); memset(num,0,sizeof(num)); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d%d",&x,&y); map[x][y]++; map[y][x]++; num[x]++; num[y]++; } counts=0; colorcont=0; int flag=0; for(int i=1;i<56;i++) { if(num[i]) {colorcont++;b=i;} if(num[i]%2!=0) {flag=1;break;} } printf("Case #%d
",k+1); if(!flag) { dfs(b); if(counts!=colorcont) printf("some beads may be lost
"); else euler(b); } else printf("some beads may be lost
"); } }

좋은 웹페이지 즐겨찾기