UVA315 Network

Graph, 절단점 찾기

출처: UVA UVA315 Network


SOL)
절단점이 될 수 있는 점의 개수를 구한 뒤 출력



[-] Collapse

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<algorithm>
using namespace std;

int visit[100];
bool isAP[100];
vector<vector<int> > adj;
int num, cnt, result;

void init(){
    memset(visit, -1, sizeof(visit));
    memset(isAP, false, sizeof(isAP));
    adj.clear();
    adj = vector<vector<int> >(100);
    result = cnt = 0;
}
void adjSetting(string str){
    istringstream os(str);
    int u, v;
    os >> u;
    while (os >> v){
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}
int findAP(int here, bool isRoot){
    visit[here] = cnt++;
    int ret = visit[here];
    int child = 0;
    for (int i = 0; i < adj[here].size(); i++){
        int there = adj[here][i];
        if (visit[there] == -1){
            child++;
            //내 자식노드가 최대로 올라갈 수 있는 번호 구하기
            int subtree = findAP(there, false);
            //만약 루트가 아니면서 내 자식들이 나보다 위로 여결 되지 않았다면
            //절단점이다.
            if (!isRoot && subtree >= visit[here])
                isAP[here] = true;
            ret = min(ret, subtree);
        }
        else
            ret = min(ret, visit[there]);
    }
    //루트일때는 자식이 2개 이상 있으면 절단점이다.
    if (isRoot) isAP[here] = (child >= 2);
    return ret;
}

int main(){
    //freopen("input.txt", "r", stdin);
    string str;
    while (true){
        cin >> num;
        getline(cin, str);
        if (num == 0) break;
        init();
        while(true){
            getline(cin, str);
            if (str == "0") break;
            adjSetting(str);
        }
        for (int i = 1; i <= num; i++){
            if (visit[i] == -1) findAP(i, true);
        }
        for (int i = 1; i <= num; i++){
            if (isAP[i]) result++;
        }
        cout << result << endl;
    }
    return 0;
}