1144:Network

keyword

無向グラフ　関節点　BruteForce　C++

概要

ノード数V(<100)の無向グラフが与えられるので、関節点の個数を出力する問題。
ノード数が少ないので全てのノードを取り除いて試す。計算量O(V*E)。

vector<int> graph[102];
bool visited[102];
int N;

void dfs(int v){
    visited[v] = true;
    for(int i=0; i<graph[v].size(); i++){
        int u = graph[v][i];
        if(!visited[u])
            dfs(u);
    }
}

int solve(){
    if(N<3) return 0;
    int ans = 0;
    for(int i=0; i<N; i++){
        memset(visited, 0, sizeof(visited));
        visited[i] = true;
        dfs(i?0:1);
        bool found = false;
        for(int j=0; j<N; j++)
            if(!visited[j]) found = true;
        if(found)
            ans++;
    }
    return ans;
}