Untitled

                Never    
C
       
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

#define MAX_SIZE 5

// 구현
int edge_num(int adj_matrix[MAX_SIZE][MAX_SIZE]) {
	int ret=0; // 리턴할 변수 생성
    for(int i=0; i<MAX_SIZE; ++i){
        for(int j=0; j<MAX_SIZE; ++j){
            if(adj_matrix[i][j]==1) ret++; // 간선 연결 정보의 개수를 ret에 담음.
        }
    }
    return ret/2; // 간선 연결 정보의 개수 / 2 를 리턴.
}

// 구현
void complete_graph(int adj_matrix[MAX_SIZE][MAX_SIZE]) {
    for(int i=0; i<MAX_SIZE; ++i){
        int cnt=0; // i정점의 간선 연결 정보의 개수를 cnt에 저장.
        for(int j=0; j<MAX_SIZE; ++j){
            if(i==j) continue; // i==j이면 continue
            if(adj_matrix[i][j]==1) cnt++; // 간선 연결 정보가 있으면 cnt에 +1
        }
        if(cnt!=MAX_SIZE-1){ // i 정점이 다른 모든 정점과 연결되어있지 않으면
            printf("Non-complete graph\n");
            return; // 출력 후 함수 종료
        }
    }
    printf("complete graph\n"); // 모든 정점이 각각 다른 모든 정점과 연결되어 있음.
}


// 구현
void check_simple_path(int adj_matrix[MAX_SIZE][MAX_SIZE], char path[]) {
    bool flag=true; // simple path 여부를 flag에 저장.
    int visited[MAX_SIZE]={0,}; // 정점 방문 여부를 visited에 저장.
    visited[path[0]-'0']=1; // 가장 처음 방문 정점 여부를 1로 채움.
    for(int i=1; path[i]!='\0'; ++i){ // path 끝에 도달할 때 까지
        int prev=path[i-1]-'0'; // 이전 방문 정점을 prev에 저장.
        int cur =path[i]-'0'; // 현재 방문 정점을 cur에 저장.
        if(adj_matrix[prev][cur]!=1) flag=false; // prev에서 cur로 갈 수 없으면 실패.
        if(visited[cur]==1) flag=false; // 이미 cur을 방문했었다면 실패
        visited[cur]=1; // cur 방문 여부를 1로 채움.
    }
    if(flag) printf("Yes\n"); // simple path 여부에 따라 결과 출력.
    else printf("No\n");
}

int dfs(int x, int visited[MAX_SIZE], int adj_matrix[MAX_SIZE][MAX_SIZE]){ // get_largest_connected_component()에 필요한 dfs 함수.
    visited[x]=1; // 현재 정점 방문했다고 기록.
    int ret=0; // 현재 정점을 포함해서 dfs로 방문한 정점의 개수를 ret에 저장.
    for(int i=0; i<MAX_SIZE; ++i){ // 현재 정점 x에 대해 간선 정보 탐색.
        if(x==i) continue; // x와 i가 같으면 continue
        if(adj_matrix[x][i]==1 && !visited[i]){ // 간선 연결 정보가 있고, 아직 방문하지 않은 정점이면
            int temp=dfs(i, visited, adj_matrix); // temp에 dfs로 방문한 정점의 개수를 저장.
            ret+=temp; // ret에 temp 추가.
        }
    }
    return ret+1; // 현재 정점도 포함시켜줘야 하므로 ret에 +1해준 값을 리턴.
}
// 구현
int get_largest_connected_component(int adj_matrix[MAX_SIZE][MAX_SIZE]) {
    int ret=0; // 가장 큰 연결요소의 정점의 수를 담는 변수.
    for(int i=0; i<MAX_SIZE; ++i){ // 모든 정점에 대해
        int visited[MAX_SIZE]={0,}; // 정점 방문 여부를 체크하는 visited배열 선언 및 초기화.
        int temp=dfs(i, visited, adj_matrix); // temp에 i정점에 연결된 연결요소의 정점의 수를 저장.
        if(ret<temp) ret=temp; // temp가 최댓값이라면, ret 갱신
    }
    return ret; // ret 리턴.
}


int main() {

	int G1[MAX_SIZE][MAX_SIZE] = {
		{ 0, 1, 1, 0, 1 },
		{ 1, 0, 1, 0, 0 },
		{ 1, 1, 0, 1, 1 },
		{ 0, 0, 1, 0, 1 },
		{ 1, 0, 1, 1, 0 } };

	int G2[MAX_SIZE][MAX_SIZE] = {
		{ 0, 1, 1, 1, 1 },
		{ 1, 0, 0, 0, 0 },
		{ 1, 0, 0, 0, 0 },
		{ 1, 0, 0, 0, 0 },
		{ 1, 0, 0, 0, 0 } };

	int G3[MAX_SIZE][MAX_SIZE] = {
		{ 0, 1, 0, 0, 1 },
		{ 1, 0, 1, 0, 0 },
		{ 0, 1, 0, 1, 0 },
		{ 0, 0, 1, 0, 1 },
		{ 1, 0, 0, 1, 0 } };

	int G4[MAX_SIZE][MAX_SIZE] = {
		{ 0, 1, 0, 0, 0 },
		{ 1, 0, 1, 0, 0 },
		{ 0, 1, 0, 0, 0 },
		{ 0, 0, 0, 0, 1 },
		{ 0, 0, 0, 1, 0 } };

    int G5[MAX_SIZE][MAX_SIZE] = {
		{ 0, 1, 1, 1, 1 },
		{ 1, 0, 1, 1, 1 },
		{ 1, 1, 0, 1, 1 },
		{ 1, 1, 1, 0, 1 },
		{ 1, 1, 1, 1, 0 } };

	char path[] = "0123";
	

	printf("1. 그래프의 총 간선의 수: %d \n", edge_num(G1));
	printf("\n");

	printf("2. Non-complete graph or complete graph: ");
	complete_graph(G5);
	printf("\n");

	printf("3. A simple path?(Yes/No): ");
	check_simple_path(G3, path);
	printf("\n");

	printf("4. 가장 큰 연결요소의 정점의 수: %d", get_largest_connected_component(G4));
	printf("\n\n");

	return 0;
}

Raw Text