POJ 3694 Network(Tarjan求割边+LCA)

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

Source

题目大意:

给出一张图,询问每次加边之后图中有多少割边

首先我们来一遍tarjan

这样实际上形成了一棵树

对于每次询问,我们找出它们的LCA

在往LCA走的过程中判断是否是割边,如果是就取消标记

LCA暴力就可以,父亲节点的信息可以在tarjan的过程中得到

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
//#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
//char BB[1 << 15], *S = BB, *T = BB;
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct node
{
    int u,v,nxt;
}edge[MAXN];
int head[MAXN],num=1;
inline void AddEdge(int x,int y)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int N,M;

int dfn[MAXN],low[MAXN],f[MAXN],deep[MAXN],tot=0;
int bridge[MAXN],ans=0;
void pre()
{
    for(int i=1;i<=N;i++) f[i]=i;
    memset(head,-1,sizeof(head));
    num=1;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(bridge,0,sizeof(bridge));
    tot=0;
    ans=0;
}
void tarjan(int now,int fa)
{
    dfn[now]=low[now]=++tot;
    for(int i=head[now];i!=-1;i=edge[i].nxt)
    {
        if(!dfn[edge[i].v]) 
        {
            deep[edge[i].v]=deep[now]+1;
            f[edge[i].v]=now;
            tarjan(edge[i].v,now);
            low[now]=min(low[now],low[edge[i].v]);
            if(low[edge[i].v]>dfn[now])
            {
                bridge[edge[i].v]=1;
                ans++;
            }
        }    
        else if(edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]); 
    }
}
int Solve(int x,int y)
{
    if(deep[x]<deep[y]) swap(x,y);
    while(deep[x]!=deep[y])
    {
        if(bridge[x]) ans--,bridge[x]=0;
        x=f[x];    
    } 
    while(x!=y)
    {
        if(bridge[x]) ans--,bridge[x]=0;
        if(bridge[y]) ans--,bridge[y]=0;
        x=f[x];y=f[y];
    }
    return ans;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int QWQ=0;
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        if(N==0&&M==0) break;
        printf("Case %d:\n",++QWQ);
        pre();
        for(int i=1;i<=M;i++)
        {
            int x=read(),y=read();
            AddEdge(x,y);
            AddEdge(y,x);
        }
        deep[1]=1;
        tarjan(1,0);
        int Q=read();
        while(Q--)
        {
            int x=read(),y=read();
            printf("%d\n",Solve(x,y));
        }
        putchar('\n');
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

codeforces 767A Snacktower(模拟)

A. Snacktower time limit per test:2 seconds memory limit per test:256 megabytes ...

3317
来自专栏HansBug's Lab

1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

2766
来自专栏calvin

【nodejs】让nodejs像后端mvc框架(asp.net mvc)一样处理请求--参数自动映射篇(6/8)

路由、action的扫描、发现、注册搞定之后,后来我发现在我们的action里面获取参数往往都是通过request对象来一个一个获取。同样的一行代码我们不厌其烦...

1132
来自专栏Java大联盟

Spring Data MongoDB:Repository

使用Spring Data可以帮助我们快速构建项目,非常方便,Spring Data在数据持久层已经写好了常用功能,我们只需要定义一个接口去继承Spring D...

2111
来自专栏C语言及其他语言

【每日一题】问题 1073: 弟弟的作业

你的弟弟刚做完了“100以内数的加减法”这部分的作业,请你帮他检查一下。每道题目(包括弟弟的答案)的格式为a+b=c或者a-b=c,其中a和b是作业中给出的,均...

1023
来自专栏算法与数据结构

数据结构 栈&队列

2-4 依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是( ) 删除,移动头指针; 增加,移动尾指针; 删除a,b ,...

44610
来自专栏Python中文社区

Awesome!细数10个隐藏在Python中的彩蛋

1、使用re.DEBUG查看正则表达式的匹配过程 正则表达式是Python的一大特色,但是调试起来会很痛苦,很容易得出一个bug。幸运的是,Python可以打印...

1978
来自专栏数据结构与算法

3339: Rmq Problem

Description image.png Input image.png Output image.png Sample Input 7 5 ...

33911
来自专栏开发与安全

《linux c 编程一站式学习》课后部分习题解答

1、假设变量x和n是两个正整数,我们知道x/n这个表达式的结果要取Floor,例如x是17,n是4,则结果是4。如果希望结果取Ceiling应该怎么写表达式呢?...

4086
来自专栏HansBug's Lab

1012: [JSOI2008]最大数maxnumber

1012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MB Submit: 443...

2785

扫码关注云+社区

领取腾讯云代金券