#include<iostream>
using namespace std;
#define MAX_VERTICES 2000
struct GraphNode{
int vertex;
GraphNode *link;
int mycolor;
};
struct GraphType{
int n; //정점의 개수
GraphNode *adj_list[MAX_VERTICES];
};
void graph_init(GraphType *g);
void insert_vertex(GraphType *g);
void insert_edge(GraphType *g, int start, int end);
void Graph_Display(GraphType *g);
void dfs(GraphType *g, GraphType* color, int v, int ccNum, int *cc);
int connectedComponent(GraphType *g, int n, int *cc);
int main()
{
int vertex;
cin>>vertex;
int edgenum;
cin>>edgenum;
GraphType g;
graph_init(&g);
//정점삽입
int *cc = new int[vertex];
for(int i=0; i<vertex; i++)
insert_vertex(&g);
for(int j=0 ;j<edgenum; j++)
{
int a, b;
cin>>a>>b;
insert_edge(&g, a, b);
}
cout<<connectedComponent(&g, vertex, cc)<<endl;
// Graph_Display(&g);
return 0;
}
void ccDFS(GraphType *g, GraphType* color, int v, int ccNum, int *cc)
{
color->adj_list[v]->mycolor = 9; // v를 방문하였다고 표시함
cc[v] = ccNum; // v의 연결성분 번호 설정
for (int w =1; w<=ccNum; w++)
{
if (color->adj_list[w]->mycolor == 0)
ccDFS(g, color, w, ccNum, cc);
}
color->adj_list[v]->mycolor = 5; // 종료된 상태
}
int connectedComponent(GraphType *g, int n, int *cc)
{ GraphType *color;
int v;
for(v = 0; v < n; v++)
color->adj_list[v]->mycolor = 0; // 미방문 상태
int componentNumber = 0;
for(v = 0; v < n; v++)
if (color->adj_list[v]->mycolor == 0) // v가 미방문된 경우
{ componentNumber++;
ccDFS(g, color, v, v, cc);
}
return componentNumber;
}
//그래프 초기화
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)
{g->n++;}
//간선 삽입 연산
void insert_edge(GraphType *g, int u, int v)
{
GraphNode *node, *vnode;
node = (GraphNode *)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = g->adj_list[u];
g->adj_list[u] = node;
//두 방향을 다 연결시키려고 하기 때문에 vnode를 사용한다. (u와 v를 서로연결)
vnode = (GraphNode*)malloc(sizeof(GraphNode));
vnode->vertex = u;
vnode->link = g->adj_list[v];
g->adj_list[v]=vnode;
}
일단 인접리스트는 양방향으로 구현했는데
이게 임의의 두 도시 사이에 가는 경로가 존재하는 가장 큰 도시 지합의 도시수를 출력하는거라서
만약 1-2-3연결되어있고 0-4되어있으면 1-2-3이 젤크니까 요소 3 출력임<도시갯수>
근데 dfs코드에서 잘안됌.. ㅠㅠ 헬프
댓글 0