Function main

codes/c/Code_4_05_2_stack.c:16–90

bool visited[100009];

int main() {
	// 入力
	scanf("%d%d", &N, &M);
	int i;
	for (i = 1; i <= M; i++) {
		scanf("%d%d", &A[i], &B[i]);
	}
	
	// 各頂点の次数を数える（手順 1.）
	for (i = 1; i <= N; i++) degree[i] = 0;
	for (i = 1; i <= M; i++) {
		degree[A[i]] += 1;
		degree[B[i]] += 1;
	}
	
	// 隣接リスト G の構築（手順 2.）
	for (i = 1; i <= N; i++) {
		G[i] = (int*)malloc(degree[i] * sizeof(int));
	}
	
	// G に辺の情報を追加していく（手順 3.）
	for (i = 1; i <= N; i++) cnt[i] = 0;
	for (i = 1; i <= M; i++) {
		G[A[i]][cnt[A[i]]] = B[i];
		cnt[A[i]] += 1;
		G[B[i]][cnt[B[i]]] = A[i];
		cnt[B[i]] += 1;
	}
	
	
	// スタック S の定義
	// スタックの中身が S[0], S[1], ..., S[SZ - 1] になるようにする
	int S[100009], SZ = 0;
	
	// 深さ優先探索の初期化
	for (i = 1; i <= N; i++) {
		visited[i] = false;
	}
	visited[1] = true;
	S[SZ] = 1; SZ++; // S に 1 を追加
	
	// 幅優先探索
	while (SZ >= 1) {
		int pos = S[SZ - 1]; // S の先頭を調べる
		SZ--; // S の先頭を取り出す
		for (i = 0; i < degree[pos]; i++) {
			int nex = G[pos][i];
			if (visited[nex] == false) {
				visited[nex] = true;
				S[SZ] = nex; SZ++; // S に nex を追加
			}
		}
	}
	
	// 連結かどうかの判定（Answer=true のとき連結）
	bool answer = true;
	for (int i = 1; i <= N; i++) {
		if (visited[i] == false) {