그림 의 너비 우선 스 트 리밍 시퀀스

Description

그림 (graph) 은 데이터 구조 G = (V, E) 이 고 그 중에서 V 는 G 중의 결점 의 유한 한 비공 식 집합 이 며 결점 의 비대 칭 은 변 (edge) 이다.E 는 G 중 변 의 유한 집합 이다.V = {0, 1, 2,.무방 향도 (undirected graph) 는 그림 에서 변 을 대표 하 는 짝 이 무질서 하고 무방 향도 에서 변 (u, v) 과 (v, u) 은 같은 변 을 가리킨다.
입력 변 은 무 방향 그림 을 구성 하고 정점 0 을 기점 으로 하 는 너비 우선 순 위 를 찾 습 니 다.

Input

첫 번 째 행 위 는 두 개의 정수 n, e 로 그림 의 정점 과 변 수 를 나타 낸다.아래 e 줄 은 줄 마다 두 개의 정 수 를 나타 내 고 한 변 의 출발점, 종점 을 나타 내 며 중복 되 지 않 고 실패 하지 않 음 을 보증한다.1≤n≤20，0≤e≤190

Output

앞의 n 줄 출력 은 그림 과 인접 하지 않 은 행렬 입 니 다. 마지막 줄 출력 은 정점 0 을 기점 으로 하 는 너비 로 우선 순 위 를 옮 겨 다 닙 니 다. 모든 출발점 에 대해 종점 번호 에 따라 작은 순서 에서 큰 순서 로 모든 변 을 옮 겨 다 닙 니 다.번호 마다 빈 칸 을 출력 합 니 다.

Sample Input

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

Sample Output

0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 0 1 3 2

#include<iostream>
using  namespace std;
int front,rear;
#define N 22
int map[N][N],used[N],que[N],n;

void BFS()
{
    int i;
    while(front<rear)
    {
        int x=que[front++];
        for(i=1;i<n;i++)
            if(x!=i && !used[i] && map[x][i])
            {
                que[rear++]=i;
                used[i]=1;
            }
    }
}

int main()
{
//    freopen("in.txt","r",stdin);
    int m,x,y,i,j;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        front=rear=0;
        while(m--)
        {
            scanf("%d %d",&x,&y);
            map[x][y]=1;
            map[y][x]=1;
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                printf("%d ",map[i][j]);
            printf("
");
        }

        for(i=0;i<n;i++)
        {
            if(!used[i])
                used[i]=1,que[rear++]=i,BFS();
        }
        for(i=0;i<n;i++)
            printf("%d ",que[i]);
        printf("
");
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

비귀속 이차수(전차, 중차, 후차, 잎 노드의 계산)

#pragma once #include<iostream> #include<queue> #include<stack> using namespace std; template<class T> struct BinaryTree...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

그림 의 너비 우선 스 트 리밍 시퀀스

좋은 웹페이지 즐겨찾기