프로그래머스 위클리 챌린지 9주차: 전력망을 둘로 나누기

#include <vector>
#include <cstring> // memset
#include <stack> // dfs
#include <cmath> // abs
#define MAX 101
using namespace std;

bool graph[MAX][MAX];
bool visit[MAX];
vector<int> cnts;

void dfs(int start, int n) {
	stack<int> st;
	int now = start, cnt = 0;
	if (!visit[now]) st.push(now);

	while (!st.empty()) {
		now = st.top();
		st.pop();

		if (!visit[now]) {
			visit[now] = true;
			cnt++;
			for (int i = 1; i <= n; i++) {
				if (graph[now][i] && !visit[i]) st.push(i);
			}
		}
	}
	cnts.push_back(cnt);
}

int solution(int n, vector<vector<int>> wires) {
	int answer = 9900; // max num of edges: nodes*(nodes-1)
	int i, j, a, b, size = wires.size();

	for (i = 0; i < size; i++) {
		a = wires[i][0];
		b = wires[i][1];
		graph[a][b] = true;
		graph[b][a] = true;
	}

	for (i = 0; i < size; i++) {
		// remove an edge
		a = wires[i][0];
		b = wires[i][1];
		graph[a][b] = false;
		graph[b][a] = false;
		memset(visit, false, sizeof(visit));

		// run dfs
		for (j = 1; j <= n; j++) {
			if (!visit[j]) dfs(j, n);
		}

		answer = min(answer, abs(cnts[0] - cnts[1]));

		// restore
		graph[a][b] = true;
		graph[b][a] = true;
		cnts.pop_back();
		cnts.pop_back();
	}

	return answer;
}