이거 푸는사람 천재

프로그래밍 갤러리

1/3

한 때 걸그룹 이었다는 오연서.jpg ㅇㅇ
훌쩍훌쩍 군병원 냉동고에 있는 미국 유학생 출신 이등병,,, ㅇㅇ
<데이터주의>봇치더락 성지순례 시모키타자와 편(1) 보조보조배터리
해피일본뉴스 134 더Informer
싱글벙글 카자흐스탄 CU 라면 가격 .JPG 딸근이
어제자 더불어민주당 전국 집회 wavy
싱글벙글 정체를 들킬뻔한 슈퍼맨 ㅂㅂㅂ
1학년에 여학생이 1명인 대구의 고등학교...jpg 설윤아기
어제자 차량 급발진 사고 ㅇㅇ
여자들이 좋아하는 찐따남 해설 우민희
결혼과 비혼 사이, 고민하는 청년들! 결혼을 해야 할지 아이를 낳아야 할 라이스
(블라) 훈련병 고문치사 관련 블라반응 블라탐험가페페
오싹오싹 오로나민C 뚜껑이 특이한 이유 ㅇㅇ
진호의 순수한 연애몽마들 7화 pota
훌쩍훌쩍 12사단 근황, 국민전선 성명문 ㅇㅇ

김태균이 눈물을 흘린 이유 아.. 또 야신입니까.. 작성자 : ㅇㅇ

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

조회 85 추천 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/05/27	-	-
2705821	나한테 국비하라고 하면 '고맙습니다 정부 선생님'하고 절하고 한다 [1]	40대프린이(118.235)	06.01	44	0
2705819	나랑 같이 막노동 뛸 사람 없냐? [3]	프갤러(121.172)	06.01	40	0
2705818	자본주의와 성평등 그리고 저출산 [1]	프갤러(211.234)	06.01	25	0
2705817	40대 코딩 초보가 열심히 노력하면 50살때 [6]	40대프린이(118.235)	06.01	62	0
2705816	나는내향적이야	통정희박대령	06.01	20	0
2705815	국비 가보고 싶긴 함 [5]	딱님	06.01	68	0
2705813	오늘 돼지처럼 잘 퍼잤다	ㅇㅇ(49.142)	06.01	17	0
2705810	근데 국비 <- 이거 언제부터 유행한 거냐? [9]	딱님	06.01	68	0
2705809	우울해 [5]	미쿠쟝마지스키	06.01	45	0
2705808	복부비만 탈출 어케함 [2]	캐프붕	06.01	28	0
2705806	고졸 국비 급하다고 월요일 출근하라고 전화왔다. [1]	프갤러(59.16)	06.01	51	0
2705805	분명 한국인인대 중국이 샹각난다	♥끙르가즘냥덩♥	06.01	32	1
2705804	국비가 별로라는건 이해하는데 지원금 받으려면 해야함.. [6]	딘퐁	06.01	55	0
2705803	계곡의공주 VS 감자탕장인 ㄷㅅㄷ [2]	♥끙르가즘냥덩♥	06.01	24	0
2705802	오늘 오후 내내 몸을 움직였더니 온 몸에 힘이 없다	딱님	06.01	18	0
2705801	신천지 보면 거의 북한아니냐?	프갤러(221.168)	06.01	19	0
2705800	소녀의 알몸이 최고임	류류(210.217)	06.01	22	1
2705799	김영한 백기선 토비 -> 누가 더 개발쪽으로 뛰어남? [6]	프갤러(1.232)	06.01	57	0
2705798	나님글 수집해봤자 어차피 방송에 못 내보냄	♥끙르가즘냥덩♥	06.01	19	0
2705796	고졸국비나이34 취업가능? [3]	ㅇㅇㅇ(1.237)	06.01	76	0
2705795	구글 검색결과 지역 매일 업데이트되는데 어떡하냐	프갤러(218.153)	06.01	14	0
2705794	..	프갤러(123.141)	06.01	25	0
2705793	앞으로 두 부류중에 누가 더 잘나갈 것 같음? [2]	프갤러(121.161)	06.01	60	0
2705792	스벅 배달 시켜놓고 방구 뀌는중 ㅇㅅㅇ [2]	AppHiki	06.01	30	0
2705791	부트캠프 lg유플러스 유레카 갈까말까 [1]	ㅇㅇ(125.241)	06.01	47	0
2705790	요즘같은 디지털시대에 젖까기정돈 괜찮은듯 [1]	헬마스터	06.01	29	0
2705789	IDM 좋아서 사고싶은데 컴퓨터 바꾸면 또 새로 사야되잖음 [1]	프갤러(218.153)	06.01	22	0
2705788	슈카도 역류성식도염이던데 [5]	헬마스터	06.01	54	0
2705787	일주일에 2번은 운동해야함	♥끙르가즘냥덩♥	06.01	16	0
2705786	나님 글 수집하고 스토킹하는 이유가 뭐냐? [1]	♥끙르가즘냥덩♥	06.01	23	0
2705785	개꼬시다	ㅎㅍㄴㅅ(61.98)	06.01	34	0
2705784	나는내향적이야	통정희박대령	06.01	15	0
2705783	컴퓨터 어떻게 사야할지 모르겠어요... 알려주세요 ㅜㅜㅜ [3]	ㅇㅇ(223.38)	06.01	29	0
2705782	존카맥이 AGI 개발중이다 웨얼이즈 존 코너(존카맥)	ㅇㅇ(49.142)	06.01	21	0
2705781	누구인지 몰라도 Oneclick을 사용했는데 [2]	프갤러(121.172)	06.01	38	1
2705780	해린 닮은 배우 찾음	♥끙르가즘냥덩♥	06.01	28	0
2705779	모모링 모드랑이는 부드러운 소프트아이스크림❤+	♥끙르가즘냥덩♥	06.01	17	0
2705776	연봉 8천입니다. [1]	ㅇㅇ(223.38)	06.01	52	0
2705775	군침도는 뉴비 구함 [2]	캐프붕	06.01	36	0
2705774	나님 시차를 되돌리신듯 하다 [9]	헬마스터	06.01	52	0
2705772	국비 바이럴 이제 취업홍보는 포기하고 [1]	ㅇㅇ(223.62)	06.01	42	0
2705771	오늘밤이 두렵다 [5]	멍청한유라ㅋ	06.01	48	0
2705769	몸과마음이 지친다	ㅇㅇ(49.142)	06.01	17	0
2705767	보는 눈 좋은 유라씨 어딨어 [3]	프갤러(121.183)	06.01	38	0
2705766	개발자 거품 언제쯤 꺼지냐? [4]	프갤러(59.16)	06.01	74	0
2705762	파이썬) 뉴비 이거 이해가 안되는데 할배들 도와줘요 [4]	SwiH_L	06.01	47	0
2705761	10년넘고 2억 못 벌면 ㅆㄹㄱ 개발자 맞는듯	프갤러(39.7)	06.01	31	0
2705760	국비가서 이쁜 여자 만나는 방법.	프갤러(59.16)	06.01	35	0
2705759	병신들이 착각하고 있는것 - 1. 앱 껍데기는 만들기는 쉽다 [1]	ㅇㅇ(210.98)	06.01	45	0
2705758	ㅁㅁ	프갤러(211.170)	06.01	16	0