uva-315.network(连通图的割点)

本题大意:求一个无向图额割点的个数.

本题思路:建图之后打一遍模板.

 /*************************************************************************
> File Name: uva-315.network.cpp
> Author: CruelKing
> Mail: 2016586625@qq.com
> Created Time: 2019年09月06日 星期五 17时15分07秒
本题思路:就是求图中有多少个割点
************************************************************************/ #include <cstdio>
#include <iostream>
#include <sstream>
#include <cstring>
#include <string>
using namespace std; const int maxn = + , maxm = maxn * maxn + ;
int tot, head[maxn]; struct Edge {
int to, next;
} edge[maxm]; void init() {
memset(head, -, sizeof head);
tot = ;
} void addedge(int u, int v) {
edge[tot] = (Edge) {v, head[u]}; head[u] = tot ++;
edge[tot] = (Edge) {u, head[v]}; head[v] = tot ++;
} int n;
string str; int dfn[maxn], low[maxn], stack[maxn];
bool cut[maxn], instack[maxn];
int Index, top, cut_num; void tarjan(int u, int pre) {
dfn[u] = low[u] = ++ Index;
instack[u] = true;
stack[top ++] = u;
int son = ;
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if(!dfn[v]) {
son ++;
tarjan(v, u);
if(low[u] > low[v]) low[u] = low[v];
if(pre != u && low[v] >= dfn[u]) {
cut[u] = true;
}
} else if(low[u] > dfn[v]) low[u] = dfn[v];
}
if(u == pre && son > ) {
cut[u] = true;
}
instack[u] = false;
top --;
} void solve() {
memset(dfn, , sizeof dfn);
memset(low, , sizeof low);
memset(cut, false, sizeof cut);
Index = top = cut_num = ;
for(int i = ; i <= n; i ++) {
if(!dfn[i]) tarjan(i, i);
}
for(int i = ; i <= n; i ++) if(cut[i]) cut_num ++;
printf("%d\n", cut_num);
} int main() {
int u, v;
while(~scanf("%d", &n) && n) {
init();
while(scanf("%d", &u)) {
if(u == ) break;
getline(cin, str);
stringstream ss;
ss << str;
while(ss >> v) addedge(u, v);
}
solve();
}
return ;
}
上一篇:Win10 启动64位IE浏览器——修改注册表方法


下一篇:依赖注入及AOP简述(九)——单例和无状态Scope .