이거 푸는사람 천재

프로그래밍 갤러리

1/1

북한이 오물풍선 날려주면 개이득인 이유 야옹이는 야옹해 작성자 : 포항의봄

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

조회 101 추천 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	-	-
공지	프로그래밍 갤러리 이용 안내 [71]	운영자	20.09.28	35365	62
2709519	19 ) 승무원쌕파 만든썰jpg	ㅇㅇ(125.244)	18:14	2	0
2709517	네이버 이메일 vs 지메일 [1]	qu(121.171)	18:08	7	0
2709516	진정한 개발자들만 프갤 오게 해야한다 ㅇㅅㅇ	상한포도	18:07	10	0
2709515	개발자는 아닌데 개발은 하고 IT 직무이긴 한 직업이 뭐가있지 [2]	프갤러(112.150)	18:07	20	0
2709513	19 ) 요즘 꽁떡하기 개쉬움 j pg	ㅇㅇ(125.244)	18:01	4	0
2709512	칭구..	♥냥덩수면과학연구소♥	18:01	10	0
2709511	오늘 비타민디 합성 많이 한다	발명도둑잡기	17:59	8	0
2709510	19 ) 승무원쌕파 만든썰jpg	ㅇㅇ(125.244)	17:57	3	0
2709509	좆소 = 학교 존나 봄 ㄹㅇ [26]	ㅇㅇ(223.38)	17:53	103	3
2709507	상남자 특) 깃 안쓰고 그냥 바로 소스코드 덮어써버림	프갤러(118.218)	17:49	25	0
2709506	WWDC D - 3 ㅇㅅㅇ	ㅇㅅㅇ(1.216)	17:49	6	0
2709504	19 ) 요즘 꽁떡하기 개쉬움 j pg	ㅇㅇ(210.95)	17:40	8	0
2709503	학점은행제 학사 -> 석사 어떰?	프갤러(211.234)	17:38	20	0
2709502	[참고물] 객체지향의 본질은 무엇일까요?... [2]	+abcd3421	17:38	21	1
2709501	19 ) 승무원쌕파 만든썰jpg	ㅇㅇ(210.95)	17:37	10	0
2709499	러시아 집 모습 [1]	ㅇㅇ(49.142)	17:29	30	0
2709497	C로 쉽게 풀어쓴 자료구조 이거 어떰?? [2]	ㅇㅇ(1.241)	17:27	31	0
2709496	19 ) 요즘 꽁떡하기 개쉬움 j pg	ㅇㅇ(210.95)	17:23	8	0
2709494	챗 GPT 키우기 [3]	프갤러(121.172)	17:19	49	1
2709493	ㅈ바이럴에 도배충까지	프갤러(121.170)	17:17	17	0
2709491	싱글벙글 북한이 싫어하는 K유행어	♥냥덩수면과학연구소♥	17:13	20	0
2709490	내부고발자가 무서운 이유 ㄷㄷ	ㅇㅇㅇㅇ(121.154)	17:11	14	0
2709488	나님 시작합니당✨	♥냥덩수면과학연구소♥	17:11	14	0
2709487	버퍼가 뭔지 계속듣다보니 뭔지알거같음 [1]	ㅌㅌ	17:09	32	0
2709486	개발 좆밥들아, 너네 진짜 코딩 할 줄 아냐?ㅋㅋㅋ	프갤러(220.116)	17:07	23	0
2709485	개발자 연봉? 좆도 안되는데 왜케 나대노?ㅋㅋㅋㅋㅋ	프갤러(220.116)	17:06	21	0
2709483	디자인 패턴? 뭔 개소리야 그냥 막 코딩하는게 짱이지 ㅋㅋㅋ	프갤러(220.116)	17:06	18	0
2709482	자바?틀딱 개발자들이나 쓰는거 아니노?ㅋㅋㅋ	프갤러(220.116)	17:05	14	0
2709481	깃허브? 그거 좆밥들이나 쓰는거 아님? ㅋㅋㅋ	프갤러(220.116)	17:05	12	0
2709480	씨발 파이썬? 그거 좆밥들이나 쓰는거 아니냐?ㅋㅋㅋ 진짜 능력자는 어셈블	프갤러(220.116)	17:04	11	0
2709479	개발자 연봉 1억? 좆까는 소리 ㄴㄴ 개발은 걍 취미로 하는거지 ㅇㅇ	프갤러(220.116)	17:04	9	0
2709478	깃허브? 찐따 개발자들이나 쓰는거 아니었노?ㅋㅋㅋㅋ	프갤러(220.116)	17:03	8	0
2709477	씨발, 프론트엔드 개발? 그거 개발 맞냐? 걍 웹디자인이지	프갤러(220.116)	17:03	12	0
2709475	개발 좆같이 멸망했으면 좋겠다 씨발	프갤러(220.116)	17:02	10	0
2709474	나 혼자 파이썬으로 일주일 만에 웹앱 만들었는데 ㅍㅌㅊ?	프갤러(220.116)	17:02	9	0
2709473	진짜 씨발 좆같은 프레임워크 추천좀 해줘라 개발 접게	프갤러(220.116)	17:01	7	0
2709472	야이 씨발, 파이썬? 그거 장난감 언어잖아ㅋㅋㅋㅋㅋ	프갤러(220.116)	17:01	14	0
2709471	야이 씨발 개발자들아 너네 연봉 좆도 안되는 이유 알려줄까?	프갤러(220.116)	17:00	9	0
2709470	개발 존나 쉬운데 왜케 징징대노? 걍 때려쳐라ㅋㅋㅋㅋㅋ	프갤러(220.116)	17:00	6	0
2709469	개발 좆밥들아, 너네 코드 이따구로 짤거면 때려쳐라 ㅋㅋㅋ	프갤러(220.116)	16:59	9	0
2709468	디자인 패턴? 뭔 개소리야 그냥 if else 쓰면 다 되는거 아니냐?ㅋ	프갤러(220.116)	16:59	13	0
2709466	개발 좆밥들아, 너네 진짜 코딩 할 줄 아냐?ㅋㅋㅋ	프갤러(220.116)	16:58	10	0
2709465	SI 개발? 걍 노예 아니냐? 좆소기업 탈출은 필수다 ㄹㅇ	프갤러(220.116)	16:58	10	0
2709464	프론트엔드 개발? 그거 걍 웹디자인 아니냐?ㅋㅋㅋ	프갤러(220.116)	16:56	10	0
2709463	씨발 C++ 좆같아서 때려치고 자바스크립트로 갈아탄다 ㅅㄱ	프갤러(220.116)	16:55	16	0
2709462	나 혼자 파이썬으로 일주일 만에 웹앱 만들었는데 ㅍㅌㅊ?	프갤러(220.116)	16:55	12	0
2709460	개발 좆밥들아, 너네 진짜 코딩 할 줄 아냐?ㅋㅋㅋ	프갤러(220.116)	16:54	9	0
2709458	개발 좆밥들아, 너네 진짜 코딩 할 줄 아냐?ㅋㅋㅋ	프갤러(220.116)	16:48	15	0
2709456	코딩하나만 맡기자 오천원 ~ 만원드림 [4]	프갤러(175.193)	16:45	45	0