이거 푸는사람 천재

프로그래밍 갤러리

1/1

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

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

조회 108 추천 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	-	-
2709450	야이 씨발 개발자들아 너네 연봉 좆도 안되는 이유 알려줄까?	프갤러(110.76)	06.08	20	0
2709449	디자인 패턴? 뭔 개소리야 그냥 막 코딩하는게 짱이지 ㅋㅋㅋ	프갤러(110.76)	06.08	15	0
2709448	진짜 씨발 좆같은 프레임워크 추천좀 해줘라 개발 접게	프갤러(110.76)	06.08	11	0
2709447	개발 좆밥들아, 너네 코드 이따구로 짤거면 때려쳐라 ㅋㅋㅋ	프갤러(110.76)	06.08	13	0
2709446	SI 개발? 걍 노예 아니냐? 좆소기업 탈출은 필수다 ㄹㅇ	프갤러(110.76)	06.08	16	0
2709444	개발자 연봉 1억? 좆까는 소리 ㄴㄴ 걍 평균 5천도 안됨ㅋㅋㅋ	프갤러(110.76)	06.08	16	0
2709443	컴공 나왔는데 코딩 못하면 ㄹㅇ 학교에서 뭐 배운거냐?	프갤러(110.76)	06.08	22	0
2709442	풀스택 개발자? 걍 이것저것 다 어설프게 하는 놈들 아님?	프갤러(110.76)	06.08	16	0
2709441	프론트엔드 개발? 그거 걍 웹디자인 아니냐?ㅋㅋㅋ	프갤러(110.76)	06.08	14	0
2709440	씨발 C++ 좆같아서 때려치고 자바스크립트로 갈아탄다 ㅅㄱ	프갤러(110.76)	06.08	19	0
2709439	나 혼자 파이썬으로 일주일 만에 웹앱 만들었는데 ㅍㅌㅊ? [1]	프갤러(110.76)	06.08	30	0
2709438	개발 좆밥들아, 너네 진짜 코딩 할 줄 아냐?ㅋㅋㅋ	프갤러(110.76)	06.08	23	0
2709434	취업 어려우면 OOO OO 꼭 따라 [4]	프갤러(221.150)	06.08	100	0
2709429	원래 컴공 이런곳임? [2]	ㅇㅇ(58.72)	06.08	109	0
2709427	개발자 취업 방향성 잡았음	딘퐁	06.08	49	1
2709424	평양 서울 전투기로 7분거리	ㅇㅇ(49.142)	06.08	19	0
2709422	그래서 부족한 절제력을 보완하기 위해 극한의 루틴으로 단련했어	♥냥덩수면과학연구소♥	06.08	15	0
2709421	나님은 사실 절제력이 매우 부족한 냥덩이거든..	♥냥덩수면과학연구소♥	06.08	17	0
2709420	내가 건담이다	딱국(118.235)	06.08	24	0
2709418	가이낙스 망했대..ㅇㅅㅇ [1]	헤르 미온느	06.08	31	1
2709416	된장에 마늘 먹는중 ㅇㅅㅇ [2]	AppHiki	06.08	23	0
2709414	목표치까지 7키로만 더빼면 끝 ㅇㅅㅇ	AppHiki	06.08	14	0
2709413	주말이라 인싸고닉들 안보이네 [3]	금융오지마라	06.08	42	0
2709409	ai에 대체될 생각을 하지말고	프갤러(59.7)	06.08	40	0
2709407	이거 약간 세기말감성 나서좋음 [1]	ㅇㅇ	06.08	38	0
2709405	비전공 문돌이 미래 설계 부탁해 ㅠ [5]	프갤러(39.118)	06.08	85	0
2709402	감히 나를 면접 보고 채용안한 회사 싹다 말아 먹어라!!!!!!!!!!!	프갤러(59.16)	06.08	26	0
2709400	나님 시작합니당✨	♥냥덩수면과학연구소♥	06.08	27	0
2709398	진짜 2년전까지 취업한 애들이 승자임 [2]	프갤러(112.150)	06.08	114	0
2709397	자료구조 원서 [4]	ㅇㅇ(211.234)	06.08	54	0
2709395	개발자도 ai 머신러닝 할줄 알아야함? [1]	딘퐁(14.7)	06.08	58	0
2709394	구글이랑 ms가 묘한 경쟁관계에 있는것 같다	헬마스터	06.08	30	0
2709393	개발자는 아닌데 IT회사, 직무고 개발은 하는 쪽으로 취업하러간다	프갤러(112.150)	06.08	46	0
2709392	좇센징 사장새끼들은 왜 하나같이ai 드립치고 특이점 왜치는거임??	뒤통수한방(1.213)	06.08	20	0
2709387	인생은 노력임 ㅋ	뒤통수한방(1.213)	06.08	34	0
2709386	고졸 3년차 입갤하고 연봉협상 결과 [3]	프갤러(117.111)	06.08	152	0
2709383	챗 GPT, 업무 보조용 확장 프로그램 Rx Chat Gpt [3]	프갤러(121.172)	06.08	66	1
2709381	고졸들의 유일한 희망이 부트캠프임	프갤러(14.39)	06.08	47	0
2709380	1년 넘는 취준생 ㄹㅇ 리스팩한다 [6]	프갤러(211.210)	06.08	105	0
2709378	외국계 회사 되는 야놀자 숙박객 정보도 유출?	발명도둑잡기	06.08	23	0
2709377	그레잇 정신으로 달려보자	헬마스터	06.08	18	0
2709375	나님 광묘병 걸린듯.. 침이 자꾸 흘허	♥냥덩수면과학연구소♥	06.08	21	0
2709374	부트캠프 들어갔는데 진짜 힘들어 버티기가 힘들어 주말에도 공부해야됨 [7]	프갤러(14.39)	06.08	94	0
2709368	본인이 프론트 1,2년차 주니어다 있냐 [8]	프갤러(39.117)	06.08	114	0
2709367	님들 왜 콘솔을 클릭한 후에 후킹을 하면 버벅거리나요 [1]	프갤러(115.40)	06.08	26	0
2709365	맨날 게임한하다가 부트캠프 처음가봣는데 적응이안된다... 사람들수준높아. [27]	프갤러(125.141)	06.08	189	0
2709363	애들아 놀땐 놀고 할땐 하자	프갤러(39.117)	06.08	24	0
2709357	이제 좌파는 대선후보가 없네	♥냥덩수면과학연구소♥	06.08	38	0
2709356	나님 시작합니당✨	♥냥덩수면과학연구소♥	06.08	22	0
2709353	러시아는 고졸들만 군대보내는데	프갤러(223.38)	06.08	34	0