加载中…HDU 3849 求割边 北邮邀请赛
(2011-07-18 19:21:00)
标签：
hdu3849求割边北邮邀请赛it |
分类： 图论 |
题目描述：
给你一个无向图，如果联通，给出割边。
割边求法：
如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去。
代码如下：
char
x[20];
bool
operator<(const pint &b) const
{
return strcmp(x, b.x)
< 0;
}
e[cnt].to = to;
e[cnt].next = v[from]; v[from] = cnt++;
low[id]
= dfn[id] = ++index2;
bool
flag = false;
for(int
i = v[id]; i != -1; i = e[i].next)
if (e[i].to == from
&& !flag) flag = true;
else
{
if (!dfn[e[i].to]) tarjan(e[i].to, id);
low[id] = min(low[id], low[e[i].to]);
}
index2
= 0; memset(dfn, 0, sizeof(dfn));
for(int
i = 1; i <= n; i++) if (!dfn[i]) tarjan(i,
-1);
int tmp
= 0;
memset(vst, 0, sizeof(vst));
int
head = 0, tail = 0;
que[tail++] = 1;
vst[1]
= 1; tmp++;
while(head < tail)
{
int xx = que[head++];
for(int i = v[xx]; i != -1; i
= e[i].next)
{
if (!vst[e[i].to])
{
vst[e[i].to] = 1;
tmp++;
que[tail++]
= e[i].to;
}
}
}
//cout
<< "cnt"
<< tmp
<< ' '
<< n <<
endl;
return
tmp == n;
scanf("%d", &t);
while(t--)
{
scanf("%d%d",
&n, &m);
hash.clear(); id = 1;
memset(v, -1, sizeof(v)); cnt
= 0;
for(int i = 0; i
< m; i++)
{
scanf("%s%s", tmp1.x, tmp2.x);
int id1 = hash[tmp1];
int id2 = hash[tmp2];
//cout << id1
<< ' '
<< id2
<< endl;
if (id1 == 0)
{
id1 =
hash[tmp1] = id;
rd[id++] =
tmp1;
}
if (id2 == 0)
{
id2 =
hash[tmp2] = id;
rd[id++] =
tmp2;
}
ans[i][0] = id1;
ans[i][1] = id2;
insert(id1, id2);
insert(id2, id1);
}
//cout
<< "id "
<< id
<< endl;
if (!bfs())
{
printf("0\n");
continue;
}
solve(n);
//cout
<< "hah"
<< endl;
int xx = 0;
for(int i = 0; i
< m; i++)
{
int id1 = ans[i][0], id2 = ans[i][1];
if (low[id1] > dfn[id2] ||
low[id2] > dfn[id1]) xx++;
}
printf("%d\n", xx);
//for(int i = 1; i
<= n; i++)
//
printf("%s low %d dfn %d\n", rd[i].x, low[i],
dfn[i]);
for(int i = 0; i
< m; i++)
{
int id1 = ans[i][0], id2 = ans[i][1];
if (low[id1] > dfn[id2] ||
low[id2] > dfn[id1])
printf("%s
%s\n", rd[id1].x, rd[id2].x);
}
}
return
0;
给你一个无向图，如果联通，给出割边。
割边求法：
如果low[u]>dfn[v]时，则说明u不仅不能到达v的祖先，连v也不能通过另外一条边直接到达，从而它们之间的边w(v,u)便是割边，求割边的时候有一个重边的问题要视情况处理，如果v,u之间有两条无向边，需要仍视为割边的话，则在DFS的时候加一个变量记录它的父亲,下一步遇到父结点时不扩展回去。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define SIZE 30000
struct pint
{
}tmp1, tmp2;;
pint rd[20000];
int t, n, m, id, cnt;
map<pint, int> hash;
struct edge{int to, next;}e[2000000];
int v[SIZE];
void insert(int from, int to)
{
}
int low[SIZE], dfn[SIZE], index2, ans[200000][2];
void tarjan(int id, int from)
{
}
void solve(int n)
{
}
int que[200000], vst[SIZE];
bool bfs()
{
}
int main()
{
}
喜欢
0
赠金笔