이거 푸는사람 천재

프로그래밍 갤러리

1/1

여기가 원종이 탄생갤인가요? 뭔가 께름칙한 갤이네요 작성자 : ㅇㅇ

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

조회 104 추천 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	-	-
2709564	아 시발.. ㅠㅠ 보지 좋아 ㅠㅠ	딱국(61.99)	06.08	34	0
2709563	닭장녀 닭장ㅂㅈ 냄새맡구 핥구싶당	딱국(61.99)	06.08	20	0
2709562	나 피에로님 질문받는가르뎅	흠냐롱	06.08	16	0
2709560	4050 좌빨틀딱들 빨리 좀 죽어라 [1]	♥냥덩수면과학연구소♥	06.08	27	0
2709559	닭장녀랑 ㅈㄴ 섹스하고싶다 [1]	딱국(61.99)	06.08	37	0
2709558	남자가 돈이 많고 여자가 존나 이쁘고 부질없다 [3]	류류(203.229)	06.08	47	2
2709556	스테이블 디퓨전 빌드중 ㅇㅅㅇ [2]	초코냥	06.08	43	0
2709555	여자가 나이 30넘게 애새끼 싸지르니까 조현병 낳는거 [1]	류류(203.229)	06.08	37	2
2709554	인서울 컴공야간대학원 나왔는데도 이직 힘드네 [4]	ㅇㅇ(211.36)	06.08	73	1
2709552	(240608) 프갤 정신병자 목록.txt	♥냥덩수면과학연구소♥	06.08	41	0
2709551	초크 씻어내고 보니 구멍이 생각보다 크구나 [3]	흠냐롱	06.08	36	0
2709550	플러터 웹 버그땜에 며칠째 기력을 잃으시다. [7]	헬마스터	06.08	48	0
2709549	[국가기밀] 오물 풍선 방지 작전계획 101 전격 공개	발명도둑잡기	06.08	34	0
2709547	슈카갤에 글썼다 썰렸습니다 [3]	헬마스터	06.08	43	0
2709546	adhd환자인데 개발자 할수있을까? [3]	프갤러(125.141)	06.08	46	1
2709545	야놀자 클라우드 직접 하네 [1]	발명도둑잡기	06.08	33	0
2709543	병신 갤러리 폐쇄 해라 [2]	프갤러(58.76)	06.08	43	3
2709541	나 딱지 리마 2급도 합격 [1]	딱지(211.234)	06.08	28	0
2709540	나 피에로님 오늘의 클라이밍 완료 [5]	흠냐롱	06.08	41	0
2709539	로리타 콤플렉스가 이상적인 취향임 ㅇㅅㅇ	류류(118.235)	06.08	33	1
2709537	나는내향적이야 나는조현병이야	통정희박대령	06.08	18	0
2709535	메이플+리니지 3클라+넷플릭스+vscode 컴터 견적좀 짜주세요	ㅇㅇ(223.38)	06.08	20	0
2709533	학식따리 지금 공부 [1]	ㅇㅇ	06.08	47	0
2709532	디씨인싸이드 녹음 기능 업로드 계속 안된다 [1]	발명도둑잡기	06.08	28	0
2709528	요즘 취업 존나 빡세냐?	프갤러(39.7)	06.08	45	0
2709522	백엔드 면접보는데 스프링 빈 생명주기 대답못한거 ㅈㄴ크나? [7]	프갤러(122.32)	06.08	129	0
2709521	애플이 망할 수 밖에 없는 이유 ㅇㅅㅇ	ㅇㅅㅇ(1.216)	06.08	52	0
2709517	네이버 이메일 vs 지메일 [2]	qu(121.171)	06.08	58	0
2709516	진정한 개발자들만 프갤 오게 해야한다 ㅇㅅㅇ [2]	상한포도	06.08	70	0
2709515	개발자는 아닌데 개발은 하고 IT 직무이긴 한 직업이 뭐가있지 [2]	프갤러(112.150)	06.08	88	1
2709512	칭구..	♥냥덩수면과학연구소♥	06.08	40	0
2709511	오늘 비타민디 합성 많이 한다	발명도둑잡기	06.08	26	0
2709507	상남자 특) 깃 안쓰고 그냥 바로 소스코드 덮어써버림	프갤러(118.218)	06.08	48	0
2709506	WWDC D - 3 ㅇㅅㅇ	ㅇㅅㅇ(1.216)	06.08	22	0
2709503	학점은행제 학사 -> 석사 어떰?	프갤러(211.234)	06.08	33	0
2709502	[참고물] 객체지향의 본질은 무엇일까요?... [2]	+abcd3421	06.08	51	1
2709499	러시아 집 모습 [1]	ㅇㅇ(49.142)	06.08	65	0
2709497	C로 쉽게 풀어쓴 자료구조 이거 어떰?? [2]	ㅇㅇ(1.241)	06.08	74	0
2709494	챗 GPT 키우기 [3]	프갤러(121.172)	06.08	85	1
2709493	ㅈ바이럴에 도배충까지	프갤러(121.170)	06.08	25	0
2709491	싱글벙글 북한이 싫어하는 K유행어	♥냥덩수면과학연구소♥	06.08	34	0
2709488	나님 시작합니당✨	♥냥덩수면과학연구소♥	06.08	23	0
2709487	버퍼가 뭔지 계속듣다보니 뭔지알거같음 [1]	ㅌㅌ	06.08	52	0
2709486	개발 좆밥들아, 너네 진짜 코딩 할 줄 아냐?ㅋㅋㅋ	프갤러(220.116)	06.08	32	0
2709485	개발자 연봉? 좆도 안되는데 왜케 나대노?ㅋㅋㅋㅋㅋ	프갤러(220.116)	06.08	31	0
2709483	디자인 패턴? 뭔 개소리야 그냥 막 코딩하는게 짱이지 ㅋㅋㅋ	프갤러(220.116)	06.08	28	0
2709482	자바?틀딱 개발자들이나 쓰는거 아니노?ㅋㅋㅋ	프갤러(220.116)	06.08	21	0
2709481	깃허브? 그거 좆밥들이나 쓰는거 아님? ㅋㅋㅋ	프갤러(220.116)	06.08	20	0
2709480	씨발 파이썬? 그거 좆밥들이나 쓰는거 아니냐?ㅋㅋㅋ 진짜 능력자는 어셈블	프갤러(220.116)	06.08	17	0
2709479	개발자 연봉 1억? 좆까는 소리 ㄴㄴ 개발은 걍 취미로 하는거지 ㅇㅇ	프갤러(220.116)	06.08	15	0