[双连通分量]poj 3352 Road Construction - Mr.CJ
- 博客频道 - CSDN.NET
[双连通分量]poj 3352 Road Construction
题意，求一个无向图至少要添加几条边才能成为边双连通图。
1,考虑一棵树,至少要添加(d1 + 1) / 2条边 (d1为度为1的节点数目)
2,将原图中的变连通分量缩点构造一棵树。(相同low值得点在同一个边联通分量中)
#include &stdio.h&
#include &string.h&
#include &algorithm&
#include &vector&
#define N 1024
vector&int& vec[N];
int dfn[N],low[N],vis[N],
void dfs(int u,int f)
for(int i = 0; i & vec[u].size(); ++i)
int v = vec[u][i];
if(!vis[v])
vis[v] = 1;
low[v] = dfn[v] = ++
low[u] = min(low[u],low[v]);
low[u] = min(low[u],dfn[v]);
void dfs(int u,int f)
vis[u] = 1;
dfn[u] = low[u] = tistamp ++;
for(int i = 0; i & vec[u].size(); ++i)
int v = vec[u][i];
if(v != f && vis[v] == 1)
low[u] = min(low[u],dfn[v]);
if(vis[v] == 0)
low[u] = min(low[u],low[v]);
vis[u] = 2;
int solve()
int i,k,j;
memset(vis,0,sizeof(vis));
tistamp = 1;
int deg[N];
memset(deg,0,sizeof(deg));
for(i = 1; i &= ++i)
for(j = 0; j & vec[i].size(); ++j)
k = vec[i][j];
if(low[i] != low[k])
++deg[low[i]];
++deg[low[k]];
for(i = 1; i &= ++i)
vec[i].clear();
int res = 0;
for(i = 1; i &= ++i)
if(deg[i] == 2)
return (res + 1) / 2;
int main()
int m,u,v;
scanf(&%d%d&,&n,&m);
while(m--)
scanf(&%d%d&,&u,&v);
vec[u].push_back(v);
vec[v].push_back(u);
printf(&%d\n&,solve());
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：207988次
积分：4995
积分：4995
排名：第2327名
原创：308篇
转载：24篇
评论：35条
(2)(4)(4)(8)(101)(39)(18)(40)(35)(25)(29)(1)(1)(3)(12)(2)(7)(1)根据平行得出相似三角形,推出比例式,即可求出,根据平行四边形的判定推出即可;根据等腰梯形和平行四边形的判定判断即可.
以作为条件构成的命题是真命题,证明:,,,,,四边形是平行四边形.根据作为条件构成的命题是假命题,即如果有一组对边平行,而另一组对边相等的四边形时平行四边形,如等腰梯形符合,但不是平行四边形;根据作为条件构成的命题是假命题,即如果一个四边形的对角线交于,且,,那么这个四边形时平行四边形,如图,根据已知不能推出或或,即四边形不是平行四边形.
本题考查了平行四边形的判定,相似三角形的性质和判定,等腰梯形的判定等知识点的应用,主要考查学生的推理能力哈辨析能力,题目比较好,但是一道比较容易出错的题目.
3905@@3@@@@平行四边形的判定@@@@@@259@@Math@@Junior@@$259@@2@@@@四边形@@@@@@52@@Math@@Junior@@$52@@1@@@@图形的性质@@@@@@7@@Math@@Junior@@$7@@0@@@@初中数学@@@@@@-1@@Math@@Junior@@$3956@@3@@@@命题与定理@@@@@@262@@Math@@Junior@@$262@@2@@@@命题与证明@@@@@@52@@Math@@Junior@@$52@@1@@@@图形的性质@@@@@@7@@Math@@Junior@@$7@@0@@@@初中数学@@@@@@-1@@Math@@Junior@@
@@52@@7##@@52@@7
求解答 学习搜索引擎 | 如图,四边形ABCD中,对角线AC与BD相交于点O,在\textcircled{1}AB//CD;\textcircled{2}AO=CO;\textcircled{3}AD=BC中任意选取两个作为条件,"四边形ABCD是平行四边形"为结论构造命题.(1)以\textcircled{1}\textcircled{2}作为条件构成的命题是真命题吗?若是,请证明;若不是,请举出反例;(2)写出按题意构成的所有命题中的假命题,并举出反例加以说明.(命题请写成"如果...,那么...."的形式)2942 Knights of the Round Table 点的双连通分量 + 奇圈
给出一个无向图，然后计算出该图的补图，然后再计算补图中不再任一奇圈内的点的个数。
首先要求出所有的点的双连通分量，然后判断每一个双连通分量中是否存在奇圈，若有，则该双连通分量中的任意一点均在某一个奇圈上。
求解双连通分量的方法：
设 rv[ ] 表示每个点在DFS时被访问的次序，low[ ] 表示节点 u 及其子孙所连接到点中 rv[ ] 最小的值。
首先需要一个辅助栈来存放每一个双连通分量的边。
若边( u , v )仅符合下面两种情况的任意一种则将边压入栈中：
1，v 尚未被访问。
2，rv[ v ] <= low[u] 且 v 正在等待回溯。
若当 u 的 子节点 v 回溯完成时有 low[v] >= rv[u]，则说明 u 是一个割点，此时要将栈中的在(u , v )及在其后面压入的边弹出，这些边就组成了一个点的双连通分量。
判断奇圈可以用BFS染色法。可见判断二分图的方法
代码有写的好挫。。。
#define LL long long
#define ULL unsigned long long
#define PI (acos(-1.0))
#define EPS (1e-10)
#pragma comment(linker,"/STACK:24000")
const int MAX = (1<<30);
}edge[1001000];
int head[1010];
int Top,Dfs_C
bool Is_Edge[],Is_Cut[1010],InCirle[1010],Wait_Dfs[1010];
int rv[1010],low[1010];
void Link(int u,int v)
edge[Top].v =
edge[Top].next = head[u];
head[u] = Top++;
}te[1001000];
int color[1010];
int Top_E;
void dfs(int u,int fa)
rv[u] = Dfs_C
low[u] = Dfs_Clock++;
for(int p = head[u];p != -1; p = edge[p].next)
v = edge[p].v;
E e = (E){u,v};
if(rv[v] == -1)
st.push(e);
low[u] = min(low[u],low[v]);
if(low[v] >= rv[u])
Top_E = 0;
e = st.top();
te[Top_E++] =
}while(e.u != u || e.v != v);
memset(color,-1,sizeof(color));
color[te[0].u] = 1;
color[te[0].v] = 0;
bool mark =
bool Is_Circle =
while(mark == false && Is_Circle == false)
for(int i = 0;i < Top_E; ++i)
if(color[te[i].u] == -1 && color[te[i].v] != -1)
color[te[i].u] = (color[te[i].v] == 1 ? 0 : 1);
else if(color[te[i].u] != -1 && color[te[i].v] == -1)
color[te[i].v] = (color[te[i].u] == 1 ? 0 : 1);
else if(color[te[i].u] != -1 && color[te[i].u] ==
color[te[i].v])
Is_Circle =
if(Is_Circle)
memset(color,-1,sizeof(color));
for(int i = 0;i < Top_E; ++i)
if(color[te[i].u] == -1)
color[te[i].u] = 1;
if(InCirle[te[i].u])
InCirle[te[i].u] =
if(color[te[i].v] == -1)
color[te[i].v] = 1;
if(InCirle[te[i].v])
InCirle[te[i].v] =
Is_Cut[u] =
else if(low[v] <= low[u] && v != fa && Wait_Dfs[v] == false)
st.push(e);
low[u] = min(low[u],rv[v]);
Wait_Dfs[u] =
int main()
int n,m,i,j,u,v;
while(scanf("%d %d",&n,&m) && (n||m))
for(i = 1;i <= ++i)
memset(Is_Edge[i],false,sizeof(bool)*(n+3));
for(i = 1;i <= ++i)
scanf("%d %d",&u,&v);
Is_Edge[u][v] = Is_Edge[v][u] =
memset(head,-1,sizeof(int)*(n+3));
for(i = 1;i <= ++i)
for(j = 1;j < ++j)
if(Is_Edge[i][j] == false)
Link(i,j);
Link(j,i);
memset(rv,-1,sizeof(int)*(n+3));
memset(Is_Cut,false,sizeof(bool)*(n+3));
memset(InCirle,false,sizeof(bool)*(n+3));
memset(Wait_Dfs,false,sizeof(bool)*(n+3));
Dfs_Clock = 0;
for(i = 1;i <= ++i)
if(rv[i] == -1)
dfs(i,-1);
printf("%d\n",Knight);
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。poj2942(双联通分量，交叉染色判二分图) - amourjun的专栏
- 博客频道 - CSDN.NET
题意：一些骑士，他们有些人之间有矛盾，现在要求选出一些骑士围成一圈，圈要满足如下条件：1.人数大于1。2.总人数为奇数。3.有仇恨的骑士不能挨着坐。问有几个骑士不能和任何人形成任何的圆圈。
思路：首先反向建立补图，然后问题转换成在图中找奇圈，圈肯定出现在双联通分量中，则求出图的双联通分量，又通过特性知道，一个双联通分量有奇圈则其中的点都可以出现在一个奇圈中。而对于奇圈的判定可以用交叉染色判断是非为二分图，二分图中肯定无奇圈，这里用tarjan算法得出割边（先将点入队），确定双联通分量的根节点，(对于队列中的点)然后进行染色判定，最后标记odd[]代表需要删除的点。
#include&iostream&
#include&cstring&
#include&cstdio&
#define MAXN 1004
#define MAXM 1001000
int n,m,tot,count,
int first[MAXN],DFN[MAXN],Low[MAXN],vis[MAXN],col[MAXN],mark[MAXN],stack[MAXM],odd[MAXN];
int G[MAXN][MAXN];
struct Edge
int st,to,next,
}edge[2*MAXM];
void addedge(int a,int b)
edge[tot].to=b;
edge[tot].st=a;
edge[tot].next=first[a];
edge[tot].vis=0;
first[a]=tot++;
int find(int s)
for(int i=first[s];i!=-1;i=edge[i].next)
int t=edge[i].
if(mark[t])
if(col[t]==-1)
col[t]=!col[s];
return find(t);
else if(col[t]==col[s]) return 1;
void color(int s)
memset(mark,0,sizeof(mark));
i=stack[top--];
mark[edge[i].st]=1;
mark[edge[i].to]=1;
}while(edge[i].st!=s);
memset(col,-1,sizeof(col));
if(find(s))
for(int i=1;i&=n;i++)
if(mark[i])
void dfs(int s)
DFN[s]=Low[s]=++
for(int i=first[s];i!=-1;i=edge[i].next)
int v=edge[i].
if(edge[i].vis)
edge[i].vis=edge[i^1].vis=1;
stack[++top]=i;
if(!DFN[v])
Low[s]=min(Low[s],Low[v]);
if(Low[v]&=DFN[s])color(s);
Low[s]=min(Low[s],DFN[v]);
int main()
while(scanf(&%d%d&,&n,&m),n||m)
memset(G,0,sizeof(G));
for(int i=1;i&=m;i++)
scanf(&%d%d&,&a,&b);
G[a][b]=1;
G[b][a]=1;
memset(first,-1,sizeof(first));
for(int i=1;i&=n;i++)
for(int j=i+1;j&=n;j++)
if(G[i][j]==0)
addedge(i,j);
addedge(j,i);
memset(DFN,0,sizeof(DFN));
memset(odd,0,sizeof(odd));
count=0;top=0;
for(int i=1;i&=n;i++)
if(!DFN[i])
int ans=0;
for(int i=1;i&=n;i++)
if(!odd[i])
printf(&%d\n&,ans);
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：38734次
积分：1724
积分：1724
排名：第11387名
原创：137篇
转载：12篇
(1)(1)(1)(2)(2)(3)(26)(8)(8)(17)(53)(7)(20)