https://www.acmicpc.net/problem/10451

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 20001;

int N, M; // N: 정점의 개수, M: 간선
vector<int> adj[MAX]; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

int ans = 0;

void dfs(int node) {
	if(visited[node] == 1) ans++;

	visited[node] = 1;

	for(int i = 0; i < adj[node].size(); i++) {
		int next = adj[node][i];
		if(visited[next] == 0) dfs(next);
	}
}

int main(void) {
	int k;
	cin>>k;

	for(int i = 0; i < k; i++) {
		cin>>N;

		for(int j = 1; j <= N; j++) { // 인접행렬 (j, M) (M, j)
			cin>>M;
			adj[j].push_back(M);
			adj[M].push_back(j);
		} 

		for(int j = 1; j <= N; j++)
			if(visited[j] == 0) {
				visited[j] = 1;
				dfs(j);
			}


		cout<<ans<<'\n';

		// 인접 행렬, 방문 노드, ans 초기화
		for(int j = 0; j <= N; j++) {
			adj[j].clear();
			visited[j] = 0;
			ans = 0;
		}
	}
}

https://www.acmicpc.net/problem/1707

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 20001;

int N, M; // N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점
vector<int> adj[MAX]; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:r그룹1, -1:그룹2)

void dfs(int node, int set) {
	visited[node] = set;

	for(int i = 0; i < adj[node].size(); i++) {
		int next = adj[node][i];
		if(visited[next] == 0) dfs(next, -set);
	}
}

bool bipartite() {
	for(int i = 0; i < N; i++)
		for(int j = 0; j < adj[i].size(); j++) {
			int next = adj[i][j];
			// 정점 i와 j가 연결되어 있고 둘의 그룹이 같을 경우 이분그래프가 아님
			if(visited[i] == visited[next]) return false;
		}

	return true;
}

int main(void) {
	int k;
	cin>>k;

	for(int i = 0; i < k; i++) {
		cin>>N>>M;

		int x, y; // 인접 행렬 좌표
		for(int j = 0; j < M; j++) {
			cin>>x>>y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		} 

		for(int j = 0; j <= N; j++)
			if(visited[j] == 0) {
				visited[j] = 1;
				dfs(j, 1);
			}


		if(bipartite()) cout<<"YES\n";
		else cout<<"NO\n";

		// 인접 행렬, 방문 노드 초기화
		for(int j = 0; j <= N; j++) {
			adj[j].clear();
			visited[j] = 0;
		}
	}
}

https://www.acmicpc.net/problem/11724

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;

int N, M; // N: 정점의 개수, M: 간선의 개수
int adj[MAX][MAX] = { 0, }; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

void dfs(int node) {
	for(int i = 1; i <= N; i++)
		if(adj[node][i] == 1 && visited[i] == 0) {
			visited[i] = 1;
			dfs(i);
		}
}

int main(void) {
	cin>>N>>M;

	int x, y; // 인접 행렬 좌표
	for(int i = 0; i < M; i++) {
		cin>>x>>y;
		adj[x][y] = 1;
		adj[y][x] = 1;
	}

	int ans = 0;
	for(int i = 1; i <= N; i++)
		if(visited[i] == 0) {
			dfs(i);
			ans++;
		}

	cout<<ans;

}

https://www.acmicpc.net/problem/1260

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

DFS: 깊이 우선 탐색

•시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법

•가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용

BFS: 너비 우선 탐색

시작 정점으로 부터 인접한 정점들을 모두 한 번씩 차례로 방문한 후, 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;

int N, M, V; // N: 정점의 개수, M: 간선의 개수, V: 탐색을 시작할 정점
int adj[MAX][MAX] = { 0, }; // 인접 행렬 (0:연결x, 1:연결)
int visited[MAX]; // 방문한 노드 (0:방문x, 1:방문)

void dfs(int node) {
	cout<<node<<' ';

	for(int i = 1; i <= N; i++)
		if(adj[node][i] == 1 && visited[i] == 0) {
			visited[i] = 1;
			dfs(i);
		}
}

void bfs(int node) {
	queue<int> q;
	q.push(node);
	visited[node] = 1;

	while(!q.empty()) {
		int v = q.front();
		cout<<v<<' ';
		q.pop();

		for(int i = 1; i <= N; i++)
			if(adj[v][i] == 1 && visited[i] == 0) {
				visited[i] = 1;
				q.push(i);
			}
	}
}

int main(void) {
	cin>>N>>M>>V;

	int x, y; // 인접 행렬 좌표
	for(int i = 0; i < M; i++) {
		cin>>x>>y;
		adj[x][y] = 1;
		adj[y][x] = 1;
	}

	visited[V] = 1;
	dfs(V);
	cout<<'\n';


	// 방문 노드 초기화
	for(int i = 0; i <= N; i++) visited[i] = 0;
	visited[V] = 1;
	bfs(V);
}