#include "cstdio"
#include "cmath"
#include "cstring"
#include "algorithm"
#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "set"
#include "map"
#define lson root<<1
#define rson root<<1|1
#define lowbit(i) i&(-i)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define here cout<<endl<<"_______________here "<<endl;
#define INF 0x7f7f7f7f
#define Prime 999983
#define N 2050
using namespace std;
typedef struct
{
int id, next;
}node;
node edge[N];
int n, t, idex, head[N];
int LOW[N], DFN[N], visited[N], du[N];
void addedge(int a, int b)
{
edge[t].id = b;
edge[t].next = head[a];
head[a] = t++;
}
void tarjan(int cur, int pre)
{
visited[cur] = 1;
DFN[cur] = LOW[cur] = idex++;
for(int e = head[cur]; e != -1; e = edge[e].next)
{
int to = edge[e].id;
if(to != pre && visited[to] == 1)
LOW[cur] = min(LOW[cur], DFN[to]);
if(visited[to] == 0)
{
tarjan(to, cur);
LOW[cur] = min(LOW[cur], LOW[to]);
}
}
visited[cur] = 2;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
int a, b, m, tot;
while(~scanf("%d%d", &n, &m))
{
tot = t = 0; idex = 1;
memset(du, 0, sizeof(du));
memset(LOW, 0, sizeof(LOW));
memset(DFN, 0, sizeof(DFN));
memset(head, -1, sizeof(head));
memset(visited, 0, sizeof(visited));
for(int i = 0; i < m; i++)
{
scanf("%d%d", &a, &b);
addedge(a, b);
addedge(b, a);
}
tarjan(1, 0);
for(int i = 1; i <= n; i++)
{
for(int e = head[i]; e != -1; e = edge[e].next)
{
if(LOW[i] != LOW[edge[e].id])
{
du[LOW[i]]++;
du[LOW[edge[e].id]]++;
}
}
}
for(int i = 1; i <= n; i++)
{
if(du[i] == 2)
tot++;
}
printf("%d\n", (tot + 1) / 2);
}
return 0;
}
题目的意思就是给你一张有桥的联通图， 问你最少添加几条边使这个图变成双联通图（双联通又可以分为边双联通和点双联通， 实际上双联通图就是去掉该图中的任意一个点(一条边）之后这个图还是联通的）
我们可以先求出这个图的所有双联通子图， 然后将这些双联通子图都当成一个点来看待， 这样我们原来的图就变成了一棵树， 此时我们就只需求出这棵树有多少个叶子节点， 然后将这些叶子节点两两连接起来之后原来的图就是双联通图了， 主要难点就是如何求出图的所有双联通子图 = = |
|
收藏
淘帖
踩
