이거 푸는사람 천재

프로그래밍 갤러리

1/1

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

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

조회 95 추천 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	35357	62
2709304	4050 좌파들은 범죄자도태세대	♥여래신장냥덩♥	10:40	2	0
2709303	직장 50대 한국아재의 20대 일본여자 성희롱..	프로외노자	10:38	6	0
2709302	+ 저 진짜 사소한 고민 있어요	qu(121.171)	10:37	6	0
2709301	대학에서 취준안하고 늦은놈이 망하는듯	덴분	10:36	11	0
2709300	리눅스 이거 어케쓰냐	덴분	10:35	10	0
2709299	컴퓨터를 살까말까 계속 고민만 하는 중이다... 이제 지긋지긋하다	ㅇㅇ(223.38)	10:29	5	0
2709298	우울하다..ㅇㅅㅇ	헤르 미온느	10:27	8	0
2709297	vscode에서 코드 폴딩 꼬이는거 어떻게 하냐??	프갤러(112.162)	10:24	5	0
2709296	방금 전 인스타그램 추천	발명도둑잡기	10:13	14	0
2709295	잡코는 거의 하청파견 뺑뺑이 좃소임 [1]	클갤(39.7)	10:05	20	0
2709294	ㅇㅅㅇ	♥여래신장냥덩♥	10:04	13	0
2709292	취업하고싶다 [1]	ㅇㅇ(106.102)	10:01	21	0
2709291	포케로그 개재밌는데	타입스크립트	10:00	7	0
2709290	걍 질렀음	ㅇㅇ(211.234)	09:59	12	0
2709289	모닝 알고리즘 풀엇읍니다	피에로가르뎅	09:55	15	0
2709288	옛날 젠폰에서 고장난 유심이랑 현재폰 유심이 듀얼심이되다니...	도리스아(119.195)	09:51	7	0
2709286	은행은 160개나 있네 [2]	버거띠	09:37	38	0
2709285	증권으로 검색해도 72개나 있네 [1]	버거띠	09:35	23	0
2709284	잡코리아 가니까 웹개발자 2천개 있는데 [1]	버거띠	09:33	50	1
2709283	전원 모드 바꾸는거 만들었음	ㅇㅇ(122.199)	09:31	25	0
2709282	전 여친이 자꾸 스토킹함.txt [1]	Kyle(120.17)	09:30	29	0
2709281	닭장암컷 약간 발정수컷 같은 어감임	딱국(118.235)	09:29	12	0
2709280	닭장이라고하면 진짜 개꼴리네	딱국(118.235)	09:28	18	0
2709279	나라장터 물건 보는 재미 나라장터쇼핑몰 일반인도 구매가능	도리스아(119.195)	09:25	11	0
2709278	비가 많이 온다. 나 에전에 집이 떠내려가는 꿈 꾸었는데 어디 안 나가야 [3]	도리스아(119.195)	09:16	16	0
2709277	죽엇!! 죽어엇!!	♥여래신장냥덩♥	09:11	17	0
2709276	검찰이 최근 조현옥 전 청와대 인사수석을 압수수색했습니다. 전주지검 형	검찰이 최근 조현옥 전 청와대 인사수(211.40)	09:04	13	0
2709275	현직 경찰관 B씨 강제추행 혐의로 불구속기소 된 A(54)씨에게 징역 1	현직 경찰관 B씨 강제추행 혐의로 불(211.40)	08:57	19	0
2709274	AI는 왜 벡터연산을 해야 하나? [2]	ㅇㅇ(114.30)	08:50	25	0
2709273	하루 한 번 헤르미온느 찬양	헤르 미온느	08:30	23	0
2709272	5G NR 모드 기본 사용 내 폰 5G 되는거 아님?	도리스아(119.195)	08:23	12	0
2709271	트류미 히히 ㅇㅅㅇ [1]	나트륨찡	08:22	28	0
2709270	님 노트 8 제 폰 중고가 예상 가치좀.	도리스아(119.195)	08:15	16	0
2709268	따구기 히히 [1]	딱국(61.99)	08:04	32	0
2709267	운동을 하고 그래야 하는데 [2]	주아	07:56	31	1
2709266	망갤 테스트 [4]	나트륨찡	05:55	64	3
2709263	일본에서 노트 8 팔릴까요? [4]	도리스아(119.195)	04:32	35	0
2709262	시발 갤 망햇노 [1]	프갤러(180.71)	04:28	55	0
2709259	kmooc급 찾았노 [2]	덴분	03:52	70	2
2709258	딱국이 이쁜여자랑 눈마주치면 ㄹㅇ 고양이앞의 생쥐	딱국(61.99)	03:46	21	0
2709257	전라도차별?ㅋㅋ그럼북한욕하면북한차별이냐?졷같으니까뭐라하는건데	보법E노무현	03:46	22	0
2709256	솔직히 딱국 부럽징? 섹스밖에 모르는거 히히 [1]	딱국(61.99)	03:44	40	0
2709255	아 이쁜여자가 뭐라고 이렇게나 좋은걸까	딱국(61.99)	03:39	19	0
2709254	너희들은 딱국이 보면 무슨생각들어?	딱국(61.99)	03:37	23	0
2709253	나 진짜 자해수준으로 번식올인하고있음...	딱국(61.99)	03:30	28	0
2709252	나 진짜 성욕 중증인게.. ㄹㅇㄹㅇ들어봐	딱국(61.99)	03:27	36	0
2709250	재산 축소 신고 혐의’ 이상식 의원 압수수색	B0@(211.36)	02:57	17	0
2709249	보닌 it수준 [1]	덴분	02:48	82	2
2709247	왜 리눅스에 컴파일하고 실행 동시에하는 명령어가 없는거임 [2]	ㅌㅌ	02:26	66	0