[위클리 챌린지]전력망을 둘로 나누기 C++

https://programmers.co.kr/learn/courses/30/lessons/86971

코딩테스트 연습 - 전력망을 둘로 나누기

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <cmath>

using namespace std;

int map[101][101];
int used[101] = { 0 };

int cnt;

void dfs(int a, int n) {
    used[a] = 1;
    cnt++;
    for (int i = 1; i <= n; i++) {
        if (map[a][i]==1 && used[i] == 0) {
            dfs(i, n);
        }
    }
}

int solution(int n, vector<vector<int>> wires) {
    int answer = 999;

    for (int i = 0; i < wires.size(); i++) {
        int a = wires[i][0];
        int b = wires[i][1];

        map[a][b] = 1;
        map[b][a] = 1;
    }


    for (int i = 0; i < wires.size(); i++) {
        int a = wires[i][0];
        int b = wires[i][1];

        map[a][b] = 0;
        map[b][a] = 0;

        int group[2];
        int flag = 0;

        fill(used, used + n + 1, 0);
        
        for (int j = 1; j <= n; j++) {
            if (used[j] == 0) {
                cnt = 0;
                dfs(j, n);
                group[flag] = cnt;
                flag++;
            }
        }

        map[a][b] = 1;
        map[b][a] = 1;
        answer = min(answer, abs(group[0] - group[1]));
    }

    return answer;
}