本文共 1477 字，大约阅读时间需要 4 分钟。
题目地址：
题目：输入一个n，代表有n个节点（如果n==0就结束程序运行）。
在当下n的这一组数据，可能会有若干行数据，每行先输入一个节点a, 接下来先输入一个字符，再输入一个数b，
表示a与b是连通的，如果输入的字符是空格就继续本行的输入，如果是'\n'，就结束本行的输入。（可以看本题目
最后的提示部分）
建完图后就是进行tarjan的dfs算法了，是割点的标记一下，割边就不用管了。
code：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define N 1010using namespace std;//邻接矩阵实现 求割边 割点int n;bool g[N][N];bool vis[N];int dfn[N], low[N], parent[N];bool cut_point[N]; //是不是割点void tarjan(int u){ static int counter=0; int children=0; vis[u]=true; dfn[u]=low[u]=++counter; for(int k=1; k<=n; k++){ if(g[u][k]==true){ int v=k; if(!vis[v]){ children++; parent[v]=u; tarjan(v); low[u]=min(low[u], low[v]); if(parent[u]== -1 && children >1){ cut_point[u]=true; } if(parent[u]!= -1 && low[v]>=dfn[u] ){ cut_point[u]=true; } if(low[v]>dfn[u]){ //这是割边 } } else if(v!=parent[u]){ low[u]=min(low[u], dfn[v]); } } }}int main(){ int i, j; while(scanf("%d", &n)&&n!=0 ){ int a, b; memset(g, false, sizeof(g)); memset(vis, false, sizeof(vis)); memset(parent, -1, sizeof(parent)); memset(cut_point, false, sizeof(cut_point)); while(scanf("%d", &a) && a!=0 ){ while(getchar()!='\n'){ scanf("%d", &b); g[a][b]=true; g[b][a]=true;//建立双向边 } } tarjan(1); int cnt=0; for(i=1; i<=n; i++){ if(cut_point[i]==true ){ cnt++; } } printf("%d\n", cnt ); } return 0;}
转载于:https://www.cnblogs.com/yspworld/p/4675321.html