割点的概念:对于无向图,删除这个点与其相连的边,整个图的连通分量个数增加。

对于无向图的tarjan算法,必须要设前驱~

求割点的模板~

#include<cstdio>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;
const int maxn=;
vector<int> g[maxn];
int N,M,x,y;
int low[maxn];
int dfn[maxn];
int cnt;
int scc;
int pos[maxn];
int isGedian[maxn];
int isRoot[maxn];
stack<int> st;
void init () {
fill (low,low+maxn,);
fill (dfn,dfn+maxn,);
fill (pos,pos+maxn,);
fill (isGedian,isGedian+maxn,);
for (int i=;i<maxn;i++) g[i].clear();
while (!st.empty()) st.pop();
cnt=;
scc=;
}
void tarjan (int x,int pre) {
low[x]=dfn[x]=++cnt;
int son=;
st.push(x);
for (int i=;i<g[x].size();i++) {
if (g[x][i]==pre) continue;
if (!low[g[x][i]]) {
son++;
tarjan(g[x][i],x);
low[x]=min(low[x],low[g[x][i]]);
if (x!=pre&&dfn[x]<=low[g[x][i]]) isGedian[x]=;
}
else if (!pos[g[x][i]]) low[x]=min(low[x],dfn[g[x][i]]);
}
if (low[x]==dfn[x]) {
scc++;
while () {
int u=st.top();
st.pop();
low[u]=low[x];
pos[u]=scc;
if (u==x) break;
}
}
if (x==pre&&son>) isGedian[x]=;
}
int main () {
while (scanf("%d",&N)&&N) {
init ();
while (scanf("%d",&x)&&x) {
char ch;
while ((ch=getchar())!='\n') {
scanf ("%d",&y);
g[x].push_back(y);
g[y].push_back(x);
}
}
for (int i=;i<=N;i++)
if (!low[i]) tarjan(i,i);
int gedian=;
for (int i=;i<=N;i++)
if (isGedian[i]) gedian++;
printf ("%d\n",gedian);
}
return ;
}

最新文章

  1. Atitit 知识管理的重要方法 数据来源,聚合,分类,备份,发布 搜索
  2. QinQ
  3. 【C++设计模式】单件类与DCLP(Double Check Lock Pattern)的风险
  4. javascript对象(2)
  5. iOS 静态库中使用宏定义区分iPhone模拟器与真机---备用
  6. C++中出现的计算机术语2
  7. 【LeetCode】122. Best Time to Buy and Sell Stock II
  8. tensorflow笔记(三)之 tensorboard的使用
  9. springCloud四:熔断器ribbon--Hystrix
  10. guns初级使用
  11. ECharts教程
  12. MySql 中文写入数据库乱码及Incorrect string value: &#39;\xF0\x9F...&#39; for column &#39;XXX&#39; at row 1解决
  13. 《JavaScript》 程序基本知识 数据类型。 {0912上} {0912下}
  14. 简介jsp
  15. 分布式文档系统_document查询内部原理
  16. Invalid Host header 的解决方案
  17. Qt 程序打包发布总结
  18. 一,memcached的基本概念
  19. Vundle,Vim 的 Bundle(转)
  20. java 实验一

热门文章

  1. CompletableFuture--给future调用增加回调或聚合操作
  2. AcWing 282. 石子合并
  3. AcWing 845. 八数码
  4. thinkphp一些经常用到的标签
  5. 【网易官方】极客战记(codecombat)攻略-地牢-循环又循环
  6. Windows Server 2008 R2远程桌面服务安装配置和授权激活
  7. Bugku-CTF之这是一个神奇的登陆框
  8. XSS常见攻击与防御
  9. 并发之CountDownLatch用法详解
  10. 【PAT甲级】1112 Stucked Keyboard (20分)(字符串)