题目地址:http://poj.org/problem?id=1144

题目:输入一个n,代表有n个节点(如果n==0就结束程序运行)。

在当下n的这一组数据,可能会有若干行数据,每行先输入一个节点a, 接下来先输入一个字符,再输入一个数b,

表示a与b是连通的,如果输入的字符是空格就继续本行的输入,如果是'\n',就结束本行的输入。(可以看本题目

最后的提示部分)

建完图后就是进行tarjan的dfs算法了,是割点的标记一下,割边就不用管了。

code:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#define N 1010 using 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;
}

最新文章

  1. javascript的ajax
  2. 宏定义#define的用法
  3. Spring中Ordered接口简介
  4. 获取MySQL服务提供的sakila数据库(Example Databases)
  5. 2015暑假多校联合---Expression(区间DP)
  6. js 对象 copy 对象
  7. ios 实现版本更新检查
  8. ecshop 常见问题汇总
  9. 每日一“酷”之string
  10. python函数--传参
  11. Cassandra1.2文档学习(5)—— Snitch
  12. Tomcat,Weblogic,WebSphere,JBoss四种服务器简单对比
  13. 一种计算e的方法
  14. 【甘道夫】Ubuntu群集配置 - 免费登陆
  15. Salesforce自主学习(一)
  16. Kubuntu定制开始菜单
  17. Unity3D获取资源的方法整理:
  18. Java为什么需要保留基本数据类型
  19. 在maven pom.xml中加载不同的properties ,如localhost 和 dev master等jdbc.properties 中的链接不一样
  20. app开发中的经常遇到的问题

热门文章

  1. OpenCV for Python 学习笔记 三
  2. Python环境搭建及IDE选择(转载)
  3. 定时器:Timer:System.Threading.Timer类(转)
  4. ps -ef 和 aux 区别
  5. DFS应用——找出无向图的割点
  6. C#中Dictionary的作用及用法讲解
  7. Android ImageButton的使用。
  8. 什么是bin文件?
  9. [T-SQL] 获取拼音
  10. amoeba安装与简单使用(一)