이거 푸는사람 천재

프로그래밍 갤러리

1/1

백신 접종 이후 몸에 일어나는 변화.jpg 야옹 ㅋㅋㅋㅋ 작성자 : 포항의봄.

프갤러(222.111) 2024.05.18 01:41:20

조회 106 추천 0 댓글 1

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 10

#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

typedef struct GraphNode
{
    int vertex;
    struct GraphNode *link;
} GraphNode;

typedef struct GraphType
{
    int n; // 정점의 개수
    GraphNode *adj_list[MAX_VERTICES];
} GraphType;

// 그래프 초기화
void graph_init(GraphType *g)
{
    int v;
    g->n = 0;
    for (v = 0; v < MAX_VERTICES; v++)
        g->adj_list[v] = NULL;
}
// 정점 삽입 연산
void insert_vertex(GraphType *g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES)
    {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType *g, int u, int v)
{
    GraphNode *node;
    if (u >= g->n || v >= g->n)
    {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    node = (GraphNode *)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

GraphType g;
void print_arr(int arr[], int in[], int s, int i, int size)
{
    for (int j = 0; j < g.n; j++)
        printf("%3d", in[j]);
    printf("\n");
    for (int j = 0; j < g.n; j++)
        printf("%3d", arr[j]);
    printf("  - s:%d, i:%d, size:%d\n", s, i, size);
}
void generate(int arr[], int s, int size, int *in)
{
    int i, tmp;
    int in_degree[MAX_VERTICES] = {0};
    for (i = 0; i < g.n; i++) // copy
        in_degree[i] = in[i];

    GraphNode *node = g.adj_list[arr[s]]; // 각 정점의 진입 차수를 변경
    while (node != NULL)
    {
        in_degree[node->vertex]--;
        node = node->link;
    }

    s++;
    if (s == g.n)
    {
        for (i = 0; i < g.n; i++)
            printf("정점%d->", arr[i]);
        printf("\n");
    }
    else
    {
        for (i = s; i < size; i++)
        {
            if (in_degree[arr[i]] == 0)
            {
                SWAP(arr[s], arr[i], tmp);
                generate(arr, s, size, in_degree);
                SWAP(arr[s], arr[i], tmp);
            }
        }
    }
}
// 위상정렬을 수행한다.
void topo_sort()
{
    int i, tmp;
    int arr[MAX_VERTICES], size;
    int in_degree[MAX_VERTICES];

    // 모든 정점의 진입 차수를 계산
    for (i = 0; i < g.n; i++) // 초기화
        in_degree[i] = 0;
    for (i = 0; i < g.n; i++)
    {
        GraphNode *node = g.adj_list[i]; // 정점 i에서 나오는 간선들
        while (node != NULL)
        {
            in_degree[node->vertex]++;
            node = node->link;
        }
    }
    // 진입 차수가 0인 정점을 배열에 삽입
    size = 0;
    for (i = 0; i < g.n; i++)
    {
        if (in_degree[i] == 0)
            arr[size++] = i;
    }
    // 모든 위상 순서를 생성
    for (i = 0; i < size; i++)
    {
        generate(arr, i, size, in_degree);
    }
}

int main(void)
{
    graph_init(&g);
    // 문제에 주어진 그래프에 대한 인접리스트를 완성하시오.
    insert_vertex(&g, 0);
    insert_vertex(&g, 1);
    insert_vertex(&g, 2);
    insert_vertex(&g, 3);
    insert_vertex(&g, 4);
    insert_vertex(&g, 5);

    // 정점 0의 인접 리스트 생성
    insert_edge(&g, 0, 2);
    insert_edge(&g, 0, 3);

    // 정점 1의 인접 리스트 생성
    insert_edge(&g, 1, 3);
    insert_edge(&g, 1, 4);

    // 정점 2의 인접 리스트 생성
    insert_edge(&g, 2, 3);
    insert_edge(&g, 2, 5);

    // 정점 3의 인접 리스트 생성
    insert_edge(&g, 3, 5);

    // 정점 4의 인접 리스트 생성
    insert_edge(&g, 4, 5);

    // 위상 정렬
    topo_sort();
    // 동적 메모리 반환 코드 생략
    return 0;
}
/*실제출력

*/
/*출력예시
정점0->정점1->정점2->정점4->정점3->정점5->
정점0->정점1->정점2->정점3->정점4->정점5->
정점0->정점1->정점4->정점2->정점3->정점5->
정점0->정점2->정점1->정점4->정점3->정점5->
정점0->정점2->정점1->정점3->정점4->정점5->
정점1->정점0->정점4->정점2->정점3->정점5->
정점1->정점0->정점2->정점4->정점3->정점5->
정점1->정점0->정점2->정점3->정점4->정점5->
정점1->정점4->정점0->정점2->정점3->정점5->
계속하려면 아무 키나 누르십시오 . . .
*/

아무리 생각해도 안됨

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	비난 여론에도 뻔뻔하게 잘 살 것 같은 스타는?	운영자	24/06/03	-	-
2709864	따꾹 형아 로그인 구현 도와 주세여 [1]	프갤러(116.47)	09:37	35	0
2709861	의외로 나님은 깨달아 버렸당 [1]	♥냥덩수면과학연구소♥	09:20	28	0
2709858	졸.. 려... ㅇㅅㅇ [1]	헤르 미온느	09:14	23	0
2709857	이 케이스 재발매 안 하나	☆단비☆	09:11	28	0
2709855	나님 시작합니당✨	♥냥덩수면과학연구소♥	09:05	19	0
2709854	식당에서 제육시켰는데 아지매가 간장제육 가져다줌 [1]	메쿠이로	09:04	31	0
2709851	정말 열심히했는데 왜 취업이안될까 [5]	ㅇㅇ(106.102)	09:01	57	0
2709847	하루 한 번 헤르미온느 찬양	헤르 미온느	08:54	20	0
2709846	리눅스에서 개발하는게 더 편하지않음?? [2]	프갤러(59.18)	08:45	53	1
2709845	뭔 근눅스야	ㅇㅇ	08:44	26	0
2709844	20후반고졸인데 국비부트캠프해서 취업하는게 나을까 기술직배우는게나 [6]	프갤러(125.141)	08:39	65	1
2709843	한국의 공식 운영체제는 리눅스다 ㅇㅅㅇㅋ	나트륨찡	08:39	29	0
2709842	인체의 신비..ㅇㅅㅇ [5]	헤르 미온느	08:32	44	0
2709840	928	B0@(211.36)	08:29	17	0
2709838	상상으론 공부 다하고싶은데	ㅇㅇ	08:23	21	0
2709837	프로그래머는 리눅스가 진리라고 생각했는데 꼭 그렇진 않더라 [2]	프갤러(118.218)	08:18	47	1
2709835	으 반동놈의 컴퓨터	ㅇㅇ(112.172)	08:11	14	0
2709834	오늘 아침에 일어나서 제로콜라 마시는데 심장마비 걸리는중 [4]	노력	08:10	48	0
2709833	사업자 낸지 한달 돼가는데 수입이 없네 [3]	프갤러(39.7)	08:09	46	0
2709832	모닝 개발영상하나봤다 [6]	노력	08:09	60	0
2709824	앞 뒤가 다른 냥덩	♥냥덩수면과학연구소♥	07:44	19	0
2709822	나님 인간문명 과학이 어케 이루어지는지 알아	♥냥덩수면과학연구소♥	07:40	27	0
2709817	식사란 생물에게 내려진 가장 큰 원죄이자 형벌이다	♥냥덩수면과학연구소♥	07:25	35	0
2709815	1년동안 책한권봐서 60점은 되는데 [2]	ㅇㅇ	07:21	46	0
2709813	자기객관화 [12]	ㅇㅇ	07:02	69	0
2709811	보지년들은 코딩하지마라 [3]	프갤러(104.39)	06:53	62	1
2709810	아이폰se시리즈를 아폰미니 디자인계승해야지 ㅇㅇ 가볍고 작고	♥냥덩수면과학연구소♥	06:34	26	0
2709809	맥북이야 그냥 클램쉘로 화면 연결해서 쓰면되니까 괜춘	♥냥덩수면과학연구소♥	06:32	26	0
2709808	아이폰이나 아패미니는 화면 항상 켜놓진 않기 때문애 oled도 괜춘 [3]	♥냥덩수면과학연구소♥	06:30	40	0
2709807	아퍄프로 대화면은 항상 켜놓기 때문애 oled는 부적절함	♥냥덩수면과학연구소♥	06:29	28	0
2709805	디자인만 m4아프처럼 얇고 가볍게 oled 나오면 바로 산다	♥냥덩수면과학연구소♥	06:26	24	0
2709804	아패미니에 oled 언제 들어가냐 ㅅㅂ [3]	♥냥덩수면과학연구소♥	06:23	45	0
2709803	외국도 개발자 윈도우 많이 쓰던데..ㅇㅅㅇ	ㅇㅅㅇ(106.102)	06:20	21	0
2709802	서울중앙지검을 비롯해 총 4곳에서 진행되고 있다. 전주지검 형사3부(한연	B0@(211.36)	06:07	20	0
2709801	문재인 정부가 추진한 태양광 사업 비리에 대한 검찰 수사에 속도가 붙고	B0@(211.36)	06:03	18	0
2709783	근데 반복문도 잘 못쓰는데 6년 버텼으면 [4]	프갤러(223.38)	04:36	109	2
2709778	여자친구 곧 생일이라 생일축하웹사이트 만드는중 [1]	프갤러(39.117)	04:13	48	0
2709777	이런 회사 걸러야 되냐 ? [10]	프갤러(112.150)	04:09	132	0
2709776	맥 vs 윈도우 이딴거 고민하지말고 최고 세팅알려준다 [1]	ㅇㅇ(220.76)	04:07	60	0
2709775	클로드3 claude3 유료 결제하려는데	프갤러(211.114)	04:04	27	0
2709772	요즘 국비노예들 챗비피티 쓰는거 꼴보기 싫어서 [11]	ㅇㅇ(106.101)	03:00	174	2
2709770	나 모든 원인 전부 파악함 [2]	나트륨찡	02:46	64	0
2709769	개발자 다바이스로 맥북 많이 쓰더라 외국 사람들 보면 다 맥임 [2]	프갤러(14.39)	02:45	52	0
2709768	노드 백엔드도 신입 개발자 많음? [9]	프갤러(211.234)	02:36	111	0
2709766	개발자들 맥북쓰는 이유가 머야? [9]	이시꾸	02:26	116	0
2709765	나 허리디스크인데 취업하면 회사에서 서서 근무 봐도 괜찮을까	ㅇ.ㅇ(39.7)	02:25	27	0
2709763	박스 줍는 노인 입갤이요 ㅇㅅㅇ [2]	ㅇㅅㅇ(106.102)	02:08	29	0
2709762	나 자바 대학교 과제 하는 중인데 질문있음.. [5]	ㅇㅇ(121.170)	02:01	77	0
2709761	코드기어스 아직도 나옴?	ㅇㅇ(112.172)	01:54	17	0
2709759	걍 지금 개발자 취업 시장을 딱 정리하자면 [1]	프갤러(223.38)	01:41	102	2