이거 푸는사람 천재

프로그래밍 갤러리

1/1

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

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

조회 105 추천 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	-	-
2709695	Complete [1]	도리스아(119.195)	06.08	24	0
2709694	과나-벌레들이 사는 세상	발명도둑잡기	06.08	8	0
2709692	슬슬 잠 온당.. [1]	♥냥덩수면과학연구소♥	06.08	21	0
2709689	나님 음악천재✨ [1]	♥냥덩수면과학연구소♥	06.08	13	0
2709688	뺐으 보국전자직원이 전화로 청소하려면 다 분해야 한다고	도리스아(119.195)	06.08	13	0
2709687	그래도 똘이장군보다는 도리스아가 백 배는 착하다	발명도둑잡기	06.08	12	0
2709686	오늘의 발명 실마리: 디씨인싸이드 보이스 녹음 기능 다운로더	발명도둑잡기	06.08	13	0
2709685	이거 도리랑 비슷하지? [2]	멍청한유라ㅋ	06.08	26	0
2709682	도리스아 너무 안타까운 게 [3]	발명도둑잡기	06.08	30	0
2709681	어플설치 완료 [6]	멍청한유라ㅋ	06.08	33	1
2709680	. [1/1]	♥냥덩수면과학연구소♥	06.08	21	0
2709679	프붕이 선풍기 모터분해중 [2]	도리스아(119.195)	06.08	22	0
2709677	고민)머리가 특출난거도아니고 adhd있어서 집중력 약한데.. [2]	프갤러(125.141)	06.08	26	0
2709674	나님이 만든 알고리즘으로 프갤 사용자들 이미지를 단어로 요약해냄	♥냥덩수면과학연구소♥	06.08	16	0
2709673	미니멀리스트의 캘린더 [4]	이시꾸	06.08	40	0
2709672	노무현 때 검찰이 김대중 대북 송금을 수사했던 것에 대해 도올이 비판했음 [1]	발명도둑잡기	06.08	20	0
2709669	qr코드로 출석관리하는 시스템 만들어본사람 있음? [8]	프갤러(183.98)	06.08	63	1
2709668	주말에 코딩하면 뭐하냐 ㅇㅇ? [2]	포항의봄	06.08	37	0
2709667	외계인한테 납치당하구 싶당 [1]	♥냥덩수면과학연구소♥	06.08	23	0
2709665	93-95년생들아 중딩때 여자애들한테 제일 인기 남돌 누구였음? [3]	(127.21)	06.08	29	0
2709664	프갤 친구들을 위한 노래 [1]	프갤러(118.235)	06.08	23	0
2709661	멍유 ㅅㅂ 여친이랑 주멀마다 놀러다니고 [1]	linux	06.08	28	0
2709659	나님 팬티만 입고 누은 사진 공개.. 가슴은 가렸어..	♥냥덩수면과학연구소♥	06.08	34	0
2709657	이런 ㅆㅂ 너희는 이 노래나 들어라	발명도둑잡기	06.08	17	0
2709656	나님 막담즁..✨	♥냥덩수면과학연구소♥	06.08	18	0
2709655	이분.. 사실 게이헌터일지도 몰라..	♥냥덩수면과학연구소♥	06.08	17	0
2709653	사람들이 놀러가는거 보니 [3]	멍청한유라ㅋ	06.08	39	0
2709652	몇 달 전에는 내가 흑인 음악이 저항음악이라고 칭찬하는 글 [1]	발명도둑잡기	06.08	14	0
2709651	팬티만 입으니까 춥당 옷 입구 자야지	♥냥덩수면과학연구소♥	06.08	12	0
2709649	애널의 수면영상✨	♥냥덩수면과학연구소♥	06.08	42	0
2709645	6.9mm 소추류류를 보고 화가난 여자아이	♥냥덩수면과학연구소♥	06.08	32	0
2709644	집에가는길 [4]	멍청한유라ㅋ	06.08	34	0
2709643	게이어플 쓰는 국회의원이 있다?? ㄷㅅㄷ	♥냥덩수면과학연구소♥	06.08	20	0
2709642	나는 쉬러간다 잘 있어 ㅇㅅㅇ [8]	나트륨찡	06.08	36	0
2709641	전자정부프레임워크라는게 우리가 아는 지자체 사이트들도 저걸로 만들어진거? [3]	프갤러(118.129)	06.08	41	0
2709640	구라안치고 개발자 면접 몇번 가봤는데 죄다 정장임 [3]	프갤러(112.150)	06.08	76	1
2709639	요즘 생활 루틴 ㅇㅅㅇ [8]	AppHiki	06.08	66	0
2709638	나님은 초고도 천재 대마왕임 ㅇㅅㅇㅋ [2]	나트륨찡	06.08	12	0
2709637	방금 5호선 탔는데 rain이란 모자 쓴 엄청 예쁜 백인이 [14]	발명도둑잡기	06.08	77	0
2709636	공유오피스 사무실에서 일하고 10명 20명 이런 회사 어떠냐 [2]	프갤러(112.150)	06.08	36	0
2709634	냥덩이를 만지면 벌어지는 일	♥냥덩수면과학연구소♥	06.08	22	0
2709633	개발자할려면 iq 높아야함?? [2]	프갤러(125.141)	06.08	48	1
2709632	sqld 이거 필요한거 맞음?? [4]	프갤러(222.118)	06.08	60	0
2709630	나님 팬티만 입구 누엇어양❤+ [2]	♥냥덩수면과학연구소♥	06.08	26	0
2709629	본인 목사님의 충실한 개임 [1]	ㅇㅇ(112.172)	06.08	21	0
2709628	규동에 뿌려먹는거 어디서파냐 [1]	ㅇㅇ(112.172)	06.08	12	0
2709626	해인알양 다재다능 플레이어 나트륨 ㅇㅅㅇㅋ	나트륨찡	06.08	16	0
2709625	블라보니까 코테할 때 지피티 썻다고 당당히 말하던데 ㅇㅅㅇ	포항의봄	06.08	30	0
2709623	구형 애플제품이 느려지는 이유	♥냥덩수면과학연구소♥	06.08	26	0
2709622	나님은 뱃살 대마왕임 ㅇㅅㅇ ㅋ [1]	피에로가르뎅	06.08	20	0