CRB and Graph

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 238 Accepted Submission(s): 95

Problem Description A connected, undirected graph of

N vertices and

M edges is given to CRB.
A pair of vertices (

u ,

v ) (

u <

v ) is called critical for edge

e if and only if

u and

v become disconnected by removing

e .
CRB’s task is to find a critical pair for each of

M edges. Help him!

Input There are multiple test cases. The first line of input contains an integer

T , indicating the number of test cases. For each test case:
The first line contains two integers

N ,

M denoting the number of vertices and the number of edges.
Each of the next

M lines contains a pair of integers

a and

b , denoting an undirected edge between

a and

b .
1 ≤

T ≤ 12
1 ≤

N ,

M ≤

105
1 ≤

a ,

b ≤

N
All given graphs are connected.
There are neither multiple edges nor self loops, i.e. the graph is simple.

Output For each test case, output

M lines,

i -th of them should contain two integers

u and

v , denoting a critical pair (

u ,

v ) for the

i -th edge in the input.
If no critical pair exists, output "0 0" for that edge.
If multiple critical pairs exist, output the pair with largest

u . If still ambiguous, output the pair with smallest

v .

Sample Input

Sample Output

Author KUT（DPRK）
Source 2015 Multi-University Training Contest 10

用dfs先构建一棵树，dfs类似tarjan算法，记录dfn,low值，就知道哪些边是割边。

并且割边一定在树上。同时标记哪些边是树上的边。第二次dfs就对树进行遍历。

在第一次dfs时，需要记录一个子树的第一大，第二大值。但是第一大和第二大的值

不能来自同一棵子树。这样做的目的是在第二次dfs时，当前情况下的最大值和次大值

一定不在同一联通块上。

第二次dfs时，记录两个参数n1,n2. n1是当前结点父亲，孩子，自己的最大值，其实

就是n。n2记录的是当前结点到父亲路径上，经过的所有结点最值，以及这些结点的其他

子树的最值的最值，不包括n1的。对于一条边u-v,如果dfn[v]= low[v]说明是割边，

那么就可以判定了。首先割边分两个连通块，最值分别为n1<n2答案一定是n1,n1+1.

因为n1在一边，n1+1一定在令一边，同时保证了n1是最大的。

对于割边u,v两边取最大值n1, 那么n1=n显然成立，现在就是要确定左右两个连通块谁的

最值较小，判定一下n在哪边，取另外一边的最值即可。

void work(int u,int n1,int n2){
    if(mx[u][0] > n1){
        n2 = n1;
        n1 = mx[u][0];
        if(mx[u][1] > n2)
            n2 = mx[u][1];
    }
    else if(mx[u][1] > n2){
        n2 = mx[u][1];
    }
    int m1,m2;
    for(int i = head[u];i != -1;i = edge[i].next){
        if(edge[i].ok != 2) continue;
        int v = edge[i].v;
        if(low[v] == dfn[v]){
            if(n1 == mx[v][0]){
                m1 = n2;
            }
            else {
                m1 = min(n1,mx[v][0]);
            }
            if(m1 == n) m1 = m2;
            ans[i/2][0] = m1, ans[i/2][1] = m1+1;
        }
        work(v,n1,n2);
    }
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
#define ll long long
#define maxn 300007
int head[maxn],cnt;
struct Edge{
    int v,next,ok;
};
Edge edge[maxn];
void addedge(int u,int v){
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    edge[cnt].ok = 1;
    head[u] = cnt++;
    edge[cnt].v = u;
    edge[cnt].next = head[v];
    edge[cnt].ok = 1;
    head[v] = cnt++;
}
int low[maxn],dfn[maxn],mx[maxn][2];
int dcnt=0;
void dfs(int u){
    low[u] = dfn[u] = dcnt++;
    mx[u][0]= u;
    for(int i= head[u];i != -1; i=edge[i].next){
        if(edge[i].ok == 0) continue;
        edge[i^1].ok = 0;
        int v = edge[i].v;
        if(low[v] == 0){
            edge[i].ok = 2;
            dfs(v);
            low[u] = min(low[u],low[v]);
            if(mx[v][0] > mx[u][0]){
                mx[u][1] = mx[u][0];
                mx[u][0] = mx[v][0];
            }
            else if(mx[v][0] > mx[u][1]){
                mx[u][1] = mx[v][0];
            }
        }
        else low[u] = min(low[u],low[v]);
    }
}
int ans[maxn][2],n,m;
void work(int u,int n1,int n2){
    if(mx[u][0] > n1){
        n2 = n1;
        n1 = mx[u][0];
        if(mx[u][1] > n2)
            n2 = mx[u][1];
    }
    else if(mx[u][1] > n2){
        n2 = mx[u][1];
    }
    int m1,m2;
    for(int i = head[u];i != -1;i = edge[i].next){
        if(edge[i].ok != 2) continue;
        int v = edge[i].v;
        if(low[v] == dfn[v]){
            if(n1 == mx[v][0]){
                m1 = n1;
                m2 = n2;
            }
            else {
                m1 = max(n1,mx[v][0]);
                m2 = min(n1,mx[v][0]);
            }
            if(m1 == n) m1 = m2;
            ans[i/2][0] = m1, ans[i/2][1] = m1+1;
        }
        work(v,n1,n2);
    }
}

int main(){
    int t,u,v;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        cnt = 0;
        memset(head,-1,sizeof(head));
        for(int i = 0;i < m; i++){
            scanf("%d%d",&u,&v);
            addedge(u,v);
        }
        dcnt = 1;
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        dfs(1);
        memset(ans,0,sizeof(ans));
        work(1,0,0);
        for(int i = 0;i < m; i++)
            printf("%d %d\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

秒客网

hdu 5409 CRB and Graph 2015多校联合训练赛#10 dfs

CRB and Graph

相关文章