uva 10972 RevolC FaeLoN cdoj 方老师和农场

//自己写的第一发tarjan

解:先进行双连通分解并缩点,分解后一定是一颗树,设叶节点个数为n那么答案就是(n+1)/2

关于双连通分量求解:在跑tarjan时判断每个点连向父节点的边是否是桥,如果是桥的话,该点的后代
中,未被染色的节点一点构成一个双连通分量,那么将其染色。

染色完成后依次检查每一条边的两端是

否为两种不同的颜色,如果是,所对应的颜色的度+1,最后看多少个度为1的节点就知道有多少叶子节点

也就能得到答案了。

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<string> using namespace std; const int MAXN=;
const int MAXM=; vector<int> G[MAXN];
int n,m,top,cnt1,cnt2;
bool vis[MAXN];
int color[MAXN],dfn[MAXN],low[MAXN];
int stk[MAXN];
int degree[MAXN]; void tarjan(int now,int fa){
cnt1++;
dfn[now]=low[now]=cnt1;
vis[now]=;
stk[top++]=now;
int sz=G[now].size();
for (int i=;i<sz;i++){
if (G[now][i]==fa) continue;
if (!vis[G[now][i]]){
tarjan(G[now][i],now);
low[now]=min(low[now],low[G[now][i]]);
if (low[G[now][i]]>dfn[now]){
cnt2++;
while (top>){
color[stk[--top]]=cnt2;
if (stk[top]==G[now][i]) break;
}
}
}
else{
low[now]=min(low[now],dfn[G[now][i]]);
}
}
} int main(){
while (scanf("%d%d",&n,&m)==){
cnt1=cnt2=top=;
memset(vis,,sizeof(vis));
memset(degree,,sizeof(degree));
memset(color,,sizeof(color));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(stk,,sizeof(stk));
for (int i=;i<=n;i++){
G[i].clear();
}
for (int i=;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for (int i=;i<=n;i++){
if (dfn[i]==) tarjan(i,-);
}
if (cnt2==){
printf("0\n");
continue;
}
for (int i=;i<=n;i++){
int sz=G[i].size();
for (int j=;j<sz;j++){
if (color[i]!=color[G[i][j]]){
degree[color[i]]++;
}
}
}
int ans=;
for (int i=;i<=cnt2;i++){
if (degree[i]==) ans+=;
if (degree[i]==) ans+=;
}
printf("%d\n",(ans+)/);
}
return ;
}
/*
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7 3 3
1 2
2 3
1 3 7 5
1 2
2 3
4 5
5 6
5 7
*/
上一篇:【整理】Xcode中的iOS模拟器(iOS Simulator)的介绍和使用心得


下一篇:poj 1256 Anagram(dfs)