# UVa 00315 - Network
## Online Judge

## 解題思路
就Articulation Points (p.s.題目input的解釋超爛的。)
## 解題中出現的bug
第30行的那個>=是重點，沒想仔細沒加上等於導致上傳UVa顯示 wrong answer。
## Code

#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

struct node{
    bool cut_point;
    int children;
    int d;
    int low;
    node* pi;
    vector<int> edge;
};

void Bridge_Connect(vector<node> &Graph, node &u, int &time)
{
    time++;
    u.d = time;
    u.low = time;
    for(vector<int>::iterator v = u.edge.begin();v!=u.edge.end();v++)//for	each v ∈ G.Adj[u]
    {
	    if(Graph[*v].d==0)//if	v.d == 0
        {
            u.children++;
	        Graph[*v].pi = &u;//v.pi = u
	        Bridge_Connect(Graph, Graph[*v], time);
            u.low = min(u.low, Graph[*v].low);
	        if(u.pi!=NULL && Graph[*v].low >= u.d)//if	v.low > u.d
                u.cut_point = true;
        }
		else if (u.pi != &Graph[*v])//v != u.pi
			u.low = min(u.low, Graph[*v].d);
    }
}

void Bridge_Connect(vector<node> &Graph)
{
    int cut_number = 0, time = 0;
    for(vector<node>::iterator it = Graph.begin()+1;it!=Graph.end();it++)
    {
        it->children = 0;
        it->d = 0;
        it->pi = NULL;
        it->cut_point = false;
    }
    for(vector<node>::iterator it = Graph.begin()+1;it!=Graph.end();it++)
    {
        if(it->d==0)
        {
            Bridge_Connect(Graph, *it, time);
            if(it->children>1)
                it->cut_point = true;
        }
    }
    for(vector<node>::iterator it = Graph.begin()+1;it!=Graph.end();it++)
        if(it->cut_point==true)
            cut_number++;
    cout << cut_number << endl;
}

int main()
{
    int N;//the number of the node
    while(cin>>N&&N)
    {
        cin.ignore();
        vector<node> Graph(N+1);
        string s;
        while(getline(cin, s))
        {
            stringstream ss(s);
            int u, v;
            ss >> u;
            if(!u) break;
            while(ss>>v)
            {
                Graph[u].edge.push_back(v);
                Graph[v].edge.push_back(u);
            }
        }
        Bridge_Connect(Graph);
    }
    return 0;
}

###### tags: `UVA code` `cpp` `林基成-C++` `Awwwolf的刷題之路`