이거 푸는사람 천재

프로그래밍 갤러리

1/1

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

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

조회 88 추천 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	35351	62
2709250	재산 축소 신고 혐의’ 이상식 의원 압수수색	B0@(211.36)	02:57	3	0
2709249	보닌 it수준 [1]	덴분	02:48	23	0
2709247	왜 리눅스에 컴파일하고 실행 동시에하는 명령어가 없는거임 [2]	ㅌㅌ	02:26	27	0
2709246	9급 초봉이 연3200인데 [2]	프갤러(218.234)	02:19	35	0
2709244	오라클 CASE 쓸때 CASE 바로 뒤에 참조하는거 쓰면 왜 오류남? [12]	ㅇㅇ(180.68)	01:59	40	0
2709243	자기 프로그램 만드는거 뭔가 좀 멋있지 않냐?	프갤러(14.39)	01:57	27	0
2709242	나님 좃됫어양..	♥여래신장냥덩♥	01:44	24	0
2709241	지금 코랩 나만 안 됨?	프갤러(118.223)	01:39	22	0
2709239	C, Pothon 밖에 못하겠다	덴분	01:29	36	0
2709238	"나체사진도 있는데"..고객휴대폰 집에 가져가 사진첩 훔쳐본 수리기사	발명도둑잡기	01:24	17	0
2709237	프갤 고닉들 야부리만 ㅈㄴ게 털더니 [1]	hrin(118.235)	01:22	29	0
2709236	와이파이 쓰려다 해킹?…공유기 모의해킹 해보니 “5분 만에 뚫려”	발명도둑잡기	01:19	18	0
2709230	음기 충전	발명도둑잡기	00:50	18	0
2709228	개발자 말고 다른 IT 직종 할만한게 있나 [2]	프갤러(112.150)	00:44	91	0
2709226	..	♥여래신장냥덩♥	00:41	19	0
2709225	간단한 토이 프로젝트도 포폴에 올림? [2]	프갤러(223.38)	00:40	57	0
2709224	베테랑 신입 개발자 질문 받는다	프갤러(71.204)	00:35	38	0
2709223	경력 20년차 전문 신입 HTML 개발자 질문 받는다 ㅇㅇ	프갤러(71.204)	00:33	19	0
2709222	네트워크+암호학+보안+블록체인이 기말범위인 과목이있다?!?! [1]	프갤러(112.187)	00:32	36	0
2709221	극우 차별주의자 냥덩 [1]	발명도둑잡기	00:31	31	0
2709219	30살 고졸 고민 [2]	프갤러(121.174)	00:28	57	0
2709218	비오면 장마오면 그때 에어컨 써야지	♥여래신장냥덩♥	00:27	16	0
2709217	더워서 옷 다 벗엇다	♥여래신장냥덩♥	00:20	21	0
2709216	이 사람 와꾸가 대단하다	♥여래신장냥덩♥	00:15	30	0
2709215	깨끗하게❤ 맑게⭐ 자신있게✨	♥여래신장냥덩♥	00:13	21	0
2709214	ㅅㅂ 뭐노 ㅋㅋ	♥여래신장냥덩♥	00:12	16	0
2709213	사진정리 그만하구 나님 주무십니당..	♥여래신장냥덩♥	00:09	14	0
2709211	나 국비 하는데 너네들 너무 나쁜말만 하니까 기분 다운됐어 [2]	프갤러(14.39)	00:07	54	0
2709210	ㅍ갤 개노답 3형제	♥여래신장냥덩♥	00:06	29	0
2709209	달려라 좌파야	♥여래신장냥덩♥	00:04	15	0
2709208	나님 자지 인증❤+	♥여래신장냥덩♥	00:03	36	0
2709207	사진이 만 단위니까 수작엊으로 분류하기 빡새내..	♥여래신장냥덩♥	00:01	18	0
2709206	내부직원의 고발이 무서운 이유	ㅇㅇㅇㅇㅇ(183.109)	06.07	21	0
2709205	나님은 초고도 매트릭스 기술로 지구 매트릭스 관리 중 ㅇㅅㅇ	나트륨찡	06.07	11	0
2709204	똥이 안나오네 [2]	ㅇㅇ(112.172)	06.07	22	0
2709203	중화는 속시원한것 [1]	ㅇㅇ(112.172)	06.07	19	0
2709202	나님은 지금도 지구 매트릭스 보호 중 ㅇㅅㅇ	나트륨찡	06.07	13	0
2709201	네이버 메일 vs 지메일 [1]	qu(121.171)	06.07	25	0
2709200	"'욱일기' 내건 집 현관 오물 범벅…"의사래" 신상 털기도" 관련 글	발명도둑잡기	06.07	17	0
2709199	너 지금 뭐하려구햇어? [2]	♥여래신장냥덩♥	06.07	30	0
2709197	시골에 여름에 내려가서 전원생활 하다가 올라오고 싶다 [2]	프갤러(14.39)	06.07	22	0
2709196	너네 아이큐 몇정도 나오냐 [1]	ㅇ.ㅇ(39.7)	06.07	28	0
2709195	와.. ㅅㅂ 보지에서 수박나오는짤도 있었네..	♥여래신장냥덩♥	06.07	36	0
2709194	나님 연예인 테스트 결과	♥여래신장냥덩♥	06.07	17	0
2709193	미.. 미애 바보 아니다..	♥여래신장냥덩♥	06.07	15	0
2709191	Rx시리즈가 조금씩 나아가고 있다. [4]	프갤러(121.172)	06.07	40	1
2709190	이외수 죽엇나?	♥여래신장냥덩♥	06.07	19	0
2709189	javascript에서 var 쓰면 안되는 이유 [3]	프갤러(115.139)	06.07	66	1
2709188	너 쌓여있잖아❤+	♥여래신장냥덩♥	06.07	16	0