链接：
?id=20837
?id=21278
求割顶的裸题。
UVA – 315
#include <algorithm>#include <iostream>#include <sstream>#include <cstring>#include <cstdio>#include <vector>#include <stack>#include <cmath>#include <queue>#include <map>#define lson o<<1,l,m#define rson o<<1|1,m+1,r#define mem(a) memset(a,0,sizeof(a))typedef long long ll;const int N = 100005;const int M = 105;const ll mod = 1000000009;using namespace std;int n;vector <int> G[N];int dfs_clock, bcc_cnt, pre[N], iscut[N], bcc[N];int dfs(int u, int fa) {int lowu = pre[u] = ++dfs_clock;int child = 0;for(int i = 0; i < G[u].size(); i++) {int v = G[u][i];if(pre[v] == 0) {child++;int lowv = dfs(v, u);lowu = min(lowu, lowv);if(lowv >= pre[u]) {iscut[u] = 1;}} else if(pre[v] < pre[u] && v != fa) {lowu = min(lowu, pre[v]);}}if(fa < 0 && child == 1) {iscut[u] = 0;}return lowu;}void find_bcc() {mem(pre);mem(iscut);mem(bcc);dfs_clock = bcc_cnt = 0;for(int i = 0; i < n; i++) {if(pre[i] == 0) {dfs(i, -1);}}}int main() {//freopen("in.txt", "r", stdin);while(cin >> n, n) {getchar();for(int i = 0; i < n; i++) {G[i].clear();}string line;while(getline(cin, line)) {if(line == "0") break;int x;stringstream ss(line);int ok = 1, u;while(ss >> x) {x–;//printf("%d ", x+1);if(ok) {u = x;ok = 0;} else {G[u].push_back(x);G[x].push_back(u);}}}//puts("");//for(int i = 0; i < n; i++) {//printf("%d : ", i+1);//for(int j = 0; j < G[i].size(); j++) {//printf("%d ", G[i][j] + 1);//}//puts("");//}find_bcc();int ans = 0;for(int i = 0; i < n; i++) {if(iscut[i]) ans++;}printf("%d\n", ans);}return 0;}
UVA – 10199
#include <algorithm>#include <iostream>#include <sstream>#include <cstring>#include <cstdio>#include <vector>#include <stack>#include <cmath>#include <queue>#include <map>#include <set>#define lson o<<1,l,m#define rson o<<1|1,m+1,r#define mem(a) memset(a,0,sizeof(a))typedef long long ll;const int N = 105;const int M = 10005;const ll mod = 1000000009;using namespace std;int n, m;vector <int> G[N];int dfs_clock, bcc_cnt, pre[N], iscut[N], bcc[N];int dfs(int u, int fa) {int lowu = pre[u] = ++dfs_clock;int child = 0;for(int i = 0; i < G[u].size(); i++) {int v = G[u][i];if(pre[v] == 0) {child++;int lowv = dfs(v, u);lowu = min(lowu, lowv);if(lowv >= pre[u]) {iscut[u] = 1;}} else if(pre[v] < pre[u] && v != fa) {lowu = min(lowu, pre[v]);}}if(fa < 0 && child == 1) {iscut[u] = 0;}return lowu;}void find_bcc() {mem(pre);mem(iscut);mem(bcc);dfs_clock = bcc_cnt = 0;for(int i = 0; i < n; i++) {if(pre[i] == 0) {dfs(i, -1);}}}int main() {//freopen("in.txt", "r", stdin);int ca = 1;while(cin >> n) {if(n == 0) break;for(int i = 0; i < n; i++) {G[i].clear();}map<string, int> mp;string s, t, in[N];for(int i = 0; i < n; i++) {cin >> in[i];mp[in[i]] = i;}cin >> m;for(int i = 0; i < m; i++) {cin >> s >> t;int x = mp[s];int y = mp[t];G[x].push_back(y);G[y].push_back(x);}find_bcc();int ans = 0;set<string> st;for(int i = 0; i < n; i++) {if(iscut[i]) {st.insert(in[i]);ans++;}}if(ca > 1) puts("");printf("City map #%d: %d camera(s) found\n", ca++, ans);for(set<string>::iterator it = st.begin(); it != st.end(); ++it) {cout << *it << endl;}}return 0;}
，曾经一直想让别人知道自己的心情，那些沉重，
