转自韦广:http://blog.csdn.net/weiguang_123/article/details/7538184
题目大意:每头牛希望在任意两个点u和v之间,从u到v有两条完全不同的路径。
在一个双连通块里面,任意两个点之间都有两条完全不同的路径,这里的完全不同,指的是两条路径不共享任何一条边。
这题要的是我们求出我们需要增加多少条边才能让整个图变成一整个双连通块。很明显这里不是要我们求出这里面的割点或者割边。
这题有一个做法可能比较容易理解,就是对图进行缩点,这样,一个图就变成了一棵树,然后我们记录这棵树上的叶子的数目,一个比较省边的做法是,我们将叶子两两相连,如果只有一片叶子,那我们把这片叶子与根相连即可。而在缩点过程中,我们会用到dfn(代表遍历的次序)与low(代表一个点通过自己以及其儿子可以到达的浅的点)数组,而在同一个块里面的点的所有low都是一样的,那样我们就可以通过利用那个dfn最小的点作为这个双连通块的代表,就不需要再进行缩点了。
最后,我们只需要统计入度为1的点或者块。而这样的点或者块就恰恰是我们之前讲的缩点后的叶子
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 5005
#define MAXM 100005
#define INF 1000000000
using namespace std;
bool mp[MAXN][MAXN];
int d[MAXN], dfn[MAXN], low[MAXN], vis[MAXN];
int e, head[MAXN];
int n, m, tmpdfn;
struct Edge
{
int v, next;
}edge[MAXM];
void insert(int x, int y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e++;
}
void dfs(int u, int fa)
{
vis[u] = 1;
dfn[u] = low[u] = ++tmpdfn;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(!vis[v])
{
dfs(v, u);
low[u] = min(low[u], low[v]);
}
else if(vis[v] == 1 && v != fa)
low[u] = min(low[u], dfn[v]);
}
vis[u] = 2;
}
int main()
{
scanf("%d%d", &n, &m);
e = tmpdfn = 0;
memset(head, -1, sizeof(head));
int x, y;
while(m--)
{
scanf("%d%d", &x, &y);
if(mp[x][y]) continue;
mp[x][y] = mp[y][x] = 1;
insert(x, y);
insert(y, x);
}
dfs(1, 0);
for(int i = 1; i <= n; i++)
for(int j = head[i]; j != -1; j = edge[j].next)
if(low[i] != low[edge[j].v]) d[low[i]]++;
int cnt = 0;
for(int i = 1; i <= n; i++)
if(d[i] == 1) cnt++;
printf("%d\n", (cnt + 1) / 2);
return 0;
}
分享到:
相关推荐
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1942-Paths on a Grid 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案