1341: 한 획 의 그림 문제

1924 단어 데이터 구조
[제목 설명]
만약 에 그림 에 한 획 이 존재 한다 면 한 획 의 경 로 는 오로라 로 라 고 하고 마지막 에 다시 출발점 으로 돌아간다 면 이 경 로 는 오로라 로 라 고 한다.
한 획 의 두 가지 정리 에 따 르 면 오 라 회 로 를 찾 으 면 임의의 점 에 대해 깊이 를 우선 적 으로 옮 겨 다 닌 다.오로라 로 를 찾 으 면 하나의 기이 한 점 에 대해 dfs 를 실행 합 니 다. 시간 복잡 도 는 O (m + n) 이 고 m 는 변수 이 며 n 은 포인트 입 니 다.
 
【 입력 】
첫 번 째 줄 n, m, n 개의 점, m 개의 변 이 있 고 아래 m 줄 은 각 변 이 연 결 된 두 점 을 설명 합 니 다.
【 출력 】
오 라 로 나 오 라 회 로 는 하나의 경 로 를 출력 하면 된다.
[샘플 입력]
5 5
1 2
2 3
3 4
4 5
5 1

[출력 사례]
1 5 4 3 2 1

 
사실 이 문 제 는 간단 하지만 처음에 나 는 이 문제 의 뜻 이 무엇 인지 이해 하기 어려워 서 시간 을 들 여 뜻 을 이해 했다.
 
사실 그림 의 옮 겨 다 니 는 것 은 앞의 dfs 와 bfs 의 차이 가 많 지 않다.
이 문제 와 그림 은 dfs bfs 에 많이 쓰 여 져 있 습 니 다. 다 써 봤 습 니 다.
 
알 아야 할 지식:
정리 1: 오로라 로 가 존재 하 는 조건: 그림 은 연결 되 어 있 고 두 개의 기이 한 점 만 있다.정리 2: 오로라 회로 가 존재 하 는 조건: 그림 은 연결 되 어 있 고 0 개의 기이 한 점 이 있다.
 
이 문 제 는 뒤의 승마 울타리 와 같은 유형의 문제 이기 때문에 이것 은 기초 문제 입 니 다. 이 dfs 기록 경 로 는 처음에 재 귀 적 인 역 추적 으로 인해 발생 한 것 입 니 다. 처음에 재 귀 를 스 택 으로 이해 하고 선진 적 인 후에 이 를 처리 할 수 있 습 니 다. 이 num 은 바로 이 렇 습 니 다.
먼저 기이 한 점 을 찾 아, 있 으 면 오로라 경로 임 을 설명 하고, 없 으 면 오로라 회로 임 을 설명 하 며, 오로라 경로 라면 기이 한 점 부터 시작 하고, 오로라 회로 라면 어디든지 검색 할 수 있다.
  
#include
using namespace std;
int mapp[1005][1005];
int n,m;
int s[105];
int c=0;
int num[2005];
void dfs(int i){
    for(int j=1;j<=n;j++){
        if(mapp[i][j]==1){
            mapp[i][j]=mapp[j][i]=0;
            dfs(j);
        }
    }
    num[++c]=i;
}
int main()
{
    memset(mapp,0,sizeof(mapp));
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        mapp[a][b]=mapp[b][a]=1;
        s[a]++;
        s[b]++;
    }
    int flag=1;
    for(int i=1;i<=n;i++){
        if(s[i]%2==1){
            flag=i;
        }
    }
    dfs(flag);
    for(int i=1;i<=c;i++){
        cout<

[javascript] 문자열 특징 - 문자를 배열처럼
[한화] YEP.66 – Steal & Snatch

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage