Network POJ-3694

Network POJ-3694

Description

A network administrator manages a large network. The network consists
of N computers and M links between pairs of computers. Any pair of
computers are connected directly or indirectly by successive links, so
data can be transformed between any two computers. The administrator
finds that some links are vital to the network, because failure of any
one of them can cause that data can’t be transformed between some
computers. He call such a link a bridge. He is planning to add some
new links one by one to eliminate all bridges.

You are to help the administrator by reporting the number of bridges
in the network after each new link is added.

Input

The input consists of multiple test cases. Each test case starts with
a line containing two integers N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M ≤
200,000). Each of the following M lines contains two integers A and B
( 1≤ A ≠ B ≤ N), which indicates a link between computer A and B.
Computers are numbered from 1 to N. It is guaranteed that any two
computers are connected in the initial network. The next line contains
a single integer Q ( 1 ≤ Q ≤ 1,000), which is the number of new links
the administrator plans to add to the network one by one. The i-th
line of the following Q lines contains two integer A and B (1 ≤ A ≠ B
≤ N), which is the i-th added new link connecting computer A and B.

The last test case is followed by a line containing two zeros.

Output

For each test case, print a line containing the test case number(
beginning with 1) and Q lines, the i-th of which contains a integer
indicating the number of bridges in the network after the first i new
links are added. Print a blank line after the output for each test
case.

Sample Input

3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

Sample Output

Case 1:
1
0

Case 2:
2
0

题意：

n个点，m个边
点与点之间通过边连接，如果切断某个边使得有点与其他点连接断开（连通分支增加），则称这种边为桥梁（离散上叫割边）。
接下来有Q个操作，每操作一次，输出当前存在的桥梁数量

样例分析：

我们看这个
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

一开始是图中蓝色部分，其中1和4之间的边，2和3之间的边称之为桥，再加入12边后（绿色），桥还是那俩没变，再加入43边后，桥的数量为0（因为此时你去掉任何一个边，任意两个点都可连接）

题解：

题解借鉴：
题解一

题解二

本人对lca的讲解
我又感觉并查集可以做（虽然我并没有尝试）
Tarjan缩点问题
运行一次tarjan，求出桥和缩点，那么无向图将缩点组成一个数，树边就是原本的桥。我们想要得到一颗有根树，那我们就可以在执行tarjan的时候记录每一个点父节点和深度即可
每次连接两个点，如果两个点属于同一个缩点，那连接后不会产生影响，但如果不属于一个缩点的两点u和v，连接后，我们就要找这两个点的lca，即最小公共祖先（这也是我们要得到有根树的原因），这样u->lca(u,v)->v->u将连成一个环，而里面的树边也不再是桥，路径上的点都可以缩成一个点，即合成一个分量
对于缩点的处理：
缩点相当于在一个强连通分量里的点的集合，我们在实际操作中，有两个方法使用缩点
一个是：选取一个点为实点，其余点为虚点。实点即代表着这个分量的所有信息，虚点虽然属于这个分量的点，但可以直接无视。我们要做的，就是在这个分量里选择一个点，去代表整个分量。（相当于以一个代全部）
另一方法是：对每个点都设置一个归属集合，即表示这个点属于哪一个集合。在处理的过程中，一个集合可能又会被另一个集合所包含，所以我们可以利用并查集的路径压缩，很快地找到一个点的最终所属集合。（想当于一个整体）

代码：

方法一：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const double EPS = 1e-8;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e5+10;

struct Edge
{
   
    int to, next;
}edge[MAXN*8];
int tot, head[MAXN];

int index, dfn[MAXN], low[MAXN];
int isbridge[MAXN], sum_bridge;
int fa[MAXN], depth[MAXN];

void addedge(int u, int v)
{
   
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void Tarjan(int u, int pre)
{
   
    dfn[u] = low[u] = ++index;
    depth[u] = depth[pre] + 1;  //记录深度
    fa[u] = pre;        //记录父亲结点
    for(int i = head[u]; i!=-1; i = edge[i].next)
    {
   
        int v = edge[i].to;
        if(v==pre) continue;
        if(!dfn[v])
        {
   
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v]>dfn[u])   //isbridge[v]表示在树中，以v为儿子结点的边是否为桥
                isbridge[v] = 1, sum_bridge++;
        }
        else
            low[u] = min(low[u], dfn[v]);
    }
}

void LCA(int u, int v)
{
   
    if(depth[u]<depth[v]) swap(u, v);
    while(depth[u]>depth[v])    //深度大的先往上爬。遇到桥，就把它删去。
    {
   
        if(isbridge[u]) sum_bridge--, isbridge[u] = 0;
        u = fa[u];
    }
    while(u!=v) //当深度一样时，一起爬。遇到桥，就把它删去。
    {
   
        if(isbridge[u]) sum_bridge--, isbridge[u] = 0;
        u = fa[u];
        if(isbridge[v]) sum_bridge--, isbridge[v] = 0;
        v = fa[v];
    }
}

void init()
{
   
    tot = 0;
    memset(head, -1, sizeof(head));

    index = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(isbridge, 0, sizeof(isbridge));

    sum_bridge = 0;
}

int main()
{
   
    int n, m, kase = 0;
    while(scanf("%d%d", &n, &m) && (n||m) )
    {
   
        init();
        for(int i = 1; i<=m; i++)
        {
   
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v);
            addedge(v, u);
        }

        depth[1] = 0;
        Tarjan(1, 1);
        int q, a, b;
        scanf("%d", &q);
        printf("Case %d:\n", ++kase);
        while(q--)
        {
   
            scanf("%d%d", &a, &b);
            LCA(a, b);
            printf("%d\n", sum_bridge);
        }
        printf("\n");
    }
}

方法二：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const double EPS = 1e-8;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e6+10;

struct Edge
{
   
    int to, next;
}edge[MAXN], edge0[MAXN];   //edge为初始图， edge0为重建图
int tot, head[MAXN], tot0, head0[MAXN];

int index, dfn[MAXN], low[MAXN];
int top, Stack[MAXN], instack[MAXN];
int belong[MAXN];
int fa[MAXN], depth[MAXN];  //fa用于重建图时记录当前节点的父亲节点，depth记录当前节点的深度
int sum_bridge;

//找到x最终所属的结合
int find(int x) {
    return belong[x]==x?x:belong[x]=find(belong[x]); }

void addedge(int u, int v, Edge edge[], int head[], int &tot)
{
   
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void Tarjan(int u, int pre)
{
   
    dfn[u] = low[u] = ++index;
    Stack[top++] = u;
    instack[u] = true;
    for(int i = head[u]; i!=-1; i = edge[i].next)
    {
   
        int v = edge[i].to;
        if(v==pre) continue;
        if(!dfn[v])
        {
   
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v]>dfn[u]) sum_bridge++;
        }
        else if(instack[v])
            low[u] = min(low[u], dfn[v]);
    }

    if(dfn[u]==low[u])
    {
   
        int v;
        do
        {
   
            v = Stack[--top];
            instack[v] = false;
            belong[v] = u;  //把集合的编号设为联通分量的第一个点
        }while(v!=u);
    }
}

void build(int u, int pre)
{
   
    fa[u] = pre;    //记录父亲节点
    depth[u] = depth[pre] + 1;  //记录深度
    for(int i  = head0[u]; i!=-1; i=edge0[i].next)
        if(edge0[i].to!=pre)    //防止往回走
            build(edge0[i].to, u);
}


int LCA(int u, int v)   //左一步右一步地找LCA
{
   
    if(u==v) return u;  //因为两个结点一定有LCA， 所以一定有u==v的时候

    //可能爬一步就爬了几个深度，因为中间的结点已经往上缩点了
    if(depth[u]<depth[v]) swap(u, v);   //深度大的往上爬
    sum_bridge--;
    int lca = LCA(find(fa[u]), v);
    return belong[u] = lca;     //找到了LCA，在沿路返回的时候把当前节点的所属集合置为LCA的所属集合
}

void init()
{
   
    tot = tot0 = 0;
    memset(head, -1, sizeof(head));
    memset(head0, -1, sizeof(head0));

    index = top = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(instack, 0, sizeof(instack));

    sum_bridge = 0;
}

int main()
{
   
    int n, m, kase = 0;
    while(scanf("%d%d", &n, &m) && (n||m) )
    {
   
        init();
        for(int i = 1; i<=m; i++)
        {
   
            int u, v;
            scanf("%d%d", &u, &v);
            addedge(u, v, edge, head, tot);
            addedge(v, u, edge, head, tot);
        }

        Tarjan(1, 1);
        for(int u = 1; u<=n; u++)   //重建建图
        for(int i = head[u]; i!=-1; i = edge[i].next)
        {
   
            int tmpu = find(u);
            int tmpv = find(edge[i].to);
            if(tmpu!=tmpv)
                addedge(tmpu, tmpv, edge0, head0, tot0);
        }

        depth[find(1)] = 0;
        build(find(1), find(1));    //把无根树转为有根树

        int q, a, b;
        scanf("%d", &q);
        printf("Case %d:\n", ++kase);
        while(q--)
        {
   
            scanf("%d%d", &a, &b);
            LCA(find(a), find(b));
            printf("%d\n", sum_bridge);
        }
        printf("\n");
    }
}