UVa 315. Network

2018-08-09

Description

一家電話公司在許多地方建有機房，這些機房以1到N來編號，沒有2個地方有相同的號碼。電纜線是雙向的，並且只有在機房中的交換機才可互相連接（每個機房只有一部交換機）。電話訊號可以從一個機房傳到另一個機房，但是這些機房並不一定要直接相連，它們之間的通訊可能是透過好幾個交換機。
偶爾當有停電的情況發生時，當地的機房也會因停電而無法運作。這個時候不僅這個機房的通訊中斷，可能也有其他的機房因此無法彼此通訊。在這種情況之下，我們稱這個機房為critical的。
現在你的任務就是寫一個程式幫助該公司的工程師找出在他們的系統中有多少個critical的機房。

Input Format

輸入包含多組測試資料。每組測試資料的第一列有一個整數N（N<100）。接下來最多有N列，每列的第一個整數代表某一機房的編號，而接下來的整數則代表與此機房有直接連接的機房編號。當遇到謹含一個0的一列就代表此組測試資料結束。
以Sample Input中的第一組測試資料為例說明：此例共有(5,1),(5,2),(5,3),(5,4)四個直接連線。而若以第二組測試資料為例說明：此例共有(2,1),(2,3),(5,4),(5,6),(5,2)五個直接連線。

N=0代表輸入結束。請參考Sample Input。

Output Format

對每一組測試資料，請輸出一列，含有critical機房的個數。

Sample Input

Sample Output

1
2

UVa - 315
翻譯來源：Luckycat

Solution

這題需要用到「割點」的概念，以及Tarjan Algorithm。
以下是推薦的教學影片

Code

/*************************************************************************
  > File Name: 315 - Network.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Sat Dec 30 18:02:09 2017
*************************************************************************/

#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

int N, dfs_time, ans;
int _time[101], _low[101];
vector<int> link[101];
void dfs(int input, int parent) {
    int child = 0;
    int next, size;
    bool add = false;
    size = link[input].size();
    _time[input] = _low[input] = dfs_time++;
    for (int i = 0; i < size; i++) {
        next = link[input][i];
        if (!_time[next]) {
            child++;
            dfs(next, input);
            _low[input] = min(_low[input], _low[next]);
            if (_time[input] <= _low[next])
                add = true;
        }else if (next != parent)
            _low[input] = min(_low[input], _time[next]);
    }
    if ((child >= 2 || parent) && add)
        ans++;
}
int main() {
    string line;
    int a, b;
    while (scanf("%d ", &N) && N) {
        for (int i = 0; i <= N; i++) {
            _time[i] = _low[i] = 0;
            link[i].clear();
        }
        while (getline(cin, line)) {
            stringstream ss(line);
            ss >> a;
            if (!a)
                break;
            while (ss >> b) {
                link[a].push_back(b);
                link[b].push_back(a);
            }
        }
        dfs_time = 1;
        ans = 0;
        dfs(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}