题意:
给定一幅无向图, 求出图的割点。
割点模板:http://www.cnblogs.com/Jadon97/p/8328750.html
分析:
输入有点麻烦, 用stringsteam 会比较简单
#include<cstdio> #include<iostream> #include<queue> #include<cstring> #include<string> #include<sstream> #include<map> #include<stack> #include<vector> #include<algorithm> #include<cmath> #define rep(i,a,b) for(int i = a; i < b; i++) #define _rep(i,a,b) for(int i = a; i <= b; i++) using namespace std; const int maxn = 107; vector<int> G[maxn]; int n, Index, root, ans; int dfn[maxn], low[maxn], cut[maxn]; void tarjan(int u, int father){dfn[u] = Index;low[u] = dfn[u];Index++;int child = 0;for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!dfn[v]){child++;tarjan(v, u);low[u] = min(low[v], low[u]);if(low[v] >= dfn[u] && u != root) cut[u] = 1;if(u == root && child == 2) cut[u] = 1;}else if(v != father){low[u] = min(low[u], dfn[v]);}} } int main(){ios::sync_with_stdio(false);while(cin >> n && n){Index = 1;memset(dfn, 0, sizeof(dfn));memset(low, 0, sizeof(low));memset(cut, 0, sizeof(cut));_rep(i,1,n) G[i].clear();root = 1, ans = 0;string input;while(getline(cin, input)){if(input[0] == '0') break;stringstream ss(input);int u, v;ss >> u;while(ss >> v){G[u].push_back(v);G[v].push_back(u);}}tarjan(1,1);_rep(i,1,n) if(cut[i]) ans++;cout << ans << "\n";}return 0; }