Road Construction
Description
It's
almost summer time, and that means that it's almost summer construction
time! This year, the good people who are in charge of the roads on the
tropical island paradise of Remote Island would like to repair and
upgrade the various roads that lead between the various tourist
attractions on the island.
The roads themselves are also rather
interesting. Due to the strange customs of the island, the roads are
arranged so that they never meet at intersections, but rather pass over
or under each other using bridges and tunnels. In this way, each road
runs between two specific tourist attractions, so that the tourists do
not become irreparably lost.
Unfortunately, given the nature of
the repairs and upgrades needed on each road, when the construction
company works on a particular road, it is unusable in either direction.
This could cause a problem if it becomes impossible to travel between
two tourist attractions, even if the construction company works on only
one road at any particular time.
So, the Road Department of
Remote Island has decided to call upon your consulting services to help
remedy this problem. It has been decided that new roads will have to be
built between the various attractions in such a way that in the final
configuration, if any one road is undergoing construction, it would
still be possible to travel between any two tourist attractions using
the remaining roads. Your task is to find the minimum number of new
roads necessary.
Input
The first line of input will consist of positive integers n and r, separated by a space, where 3 ≤ n ≤ 1000 is the number of tourist attractions on the island, and 2 ≤ r ≤ 1000 is the number of roads. The tourist attractions are conveniently labelled from 1 to n. Each of the following r lines will consist of two integers, v and w, separated by a space, indicating that a road exists between the attractions labelled v and w.
Note that you may travel in either direction down each road, and any
pair of tourist attractions will have at most one road directly between
them. Also, you are assured that in the current configuration, it is
possible to travel between any two tourist attractions.
Output
One line, consisting of an integer, which gives the minimum number of roads that we need to add.
Sample Input
10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10
3 3
1 2
2 3
1 3
Sample Output
2
0
題意：給出一個連通圖，求至少添加幾條邊，使得圖去掉任意一條邊，還是連通的。
強連通分量縮點生成一顆樹，求入度為1的連通分量個數n，結果為(n+1)/2；
無向圖不用像有向圖那樣考慮是否該點在棧中，因為u跟v只要有邊，說明u一定可以到到達v，v可以到達u；
而有向圖，比如1->2, 3->2,假如從1搜索到2，1跟2屬于兩個獨立的強連通分量，而從3搜到2，發現2被搜過，但2不在棧里，所以
不能使low[3] = low[2];所以無向圖的tarjan比有向圖的簡單了很多。
代碼：
#include <stdio.h>
#include <stdlib.h>
#define Min(a, b) a < b ? a : b
#define Max(a, b) a > b ? a : b
#define maxn 1001
struct edge
{
int v, next;
}fn[maxn * maxn];
int visit[maxn], g[maxn], du[maxn], low[maxn];
void set(int n)
{
for (int i = 1; i <= n; i++)
{
visit[i] = 0, g[i] = -1, du[i] = 0;
}
}
int tarjan(int f, int u, int times)
{
visit[u] = 1;
low[u] = times;
int i, v;
for (i = g[u]; i != -1; i = fn[i].next)
{
v = fn[i].v;
if (v != f)
{
if (!visit[v])
{
times = tarjan(u, v, times + 1);
low[u] = Min(low[u], low[v]);
}
low[u] = Min(low[u], low[v]);
}
}
return times;
}
int main()
{
char a[10], b[10];
int ca, n, m, th, u, v, i, times, top, k, j;
while (scanf("%d%d", &n, &m) != EOF)
{
set(n);
th = 0;
while (m--)
{
scanf("%d%d", &u, &v);
fn[th].v = v, fn[th].next = g[u], g[u] = th++;
fn[th].v = u, fn[th].next = g[v], g[v] = th++;
}
for (i = 1, times = 0; i <= n; i++)
{
if (!visit[i])
{
times = tarjan(-1, i, times + 1);
}
}
for (i = 1; i <= n; i++)
{
for (j = g[i]; j != -1; j = fn[j].next)
{
if (low[i] != low[fn[j].v])
{
du[low[i]]++;
}
}
}
for (i = 1, k = 0; i <= n; i++)
{
if (du[i] == 1)
{
k++;
}
}
printf("%d\n", (k + 1) / 2);
}
system("pause");
return 0;
}
代碼2：
#include <stdio.h>
#include <stdlib.h>
#define Min(a, b) a < b ? a : b
#define Max(a, b) a > b ? a : b
#define maxn 1001
struct edge
{
int v, next;
}fn[maxn * maxn];
int visit[maxn], scc[maxn], g[maxn], du[maxn], stack[maxn], dfn[maxn], low[maxn], top, num, hash[maxn];
void set(int n)
{
for (int i = 1; i <= n; i++)
{
visit[i] = 0, scc[i] = -1, g[i] = -1, du[i] = 0, hash[i] = 0;
}
}
int tarjan(int f, int u, int times)
{
visit[u] = 1;
stack[top++] = u;
dfn[u] = low[u] = times;
int i, v;
for (i = g[u]; i != -1; i = fn[i].next)
{
v = fn[i].v;
if (v != f)
{
if (!visit[v])
{
times = tarjan(u, v, times + 1);
low[u] = Min(low[u], low[v]);
}
else if (scc[v] == -1)
{
low[u] = Min(low[u], low[v]);
}
}
}
if (low[u] == dfn[u])
{
num++;
do
{
scc[stack[--top]] = num;
//printf("%d ", stack[top]);
}while (stack[top] != u);//printf("-=-=\n");
}
return times;
}
int main()
{
char a[10], b[10];
int ca, n, m, th, u, v, i, times, top, k, j;
scanf("%d%d", &n, &m);
set(n);
th = 0;
while (m--)
{
scanf("%d%d", &u, &v);
fn[th].v = v, fn[th].next = g[u], g[u] = th++;
fn[th].v = u, fn[th].next = g[v], g[v] = th++;
}
for (i = 1, times = 0, top = 0, num = 0; i <= n; i++)
{
if (!visit[i])
{
times = tarjan(-1, i, times);
}
}
for (i = 1; i <= n; i++)
{
hash[i] = 1;
for (j = g[i]; j != -1; j = fn[j].next)
{
if (scc[i] != scc[fn[j].v])
{
du[scc[i]]++;
}
}
}
for (i = 1, k = 0; i <= num; i++)
{
//printf("[%d] = %d ", i, du[i]);
if (du[i] == 1)
{
k++;
}
}
printf("%d\n", (k + 1) / 2);
return 0;
}