HDOJ 5409 CRB and Graph 无向图缩块
2024-08-31 19:02:32
无向图缩块后,以n所在的块为根节点,dp找每块中的最大值.
对于每一个桥的答案为两块中的较小的最大值和较小的最大值加1
CRB and Graph
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 113 Accepted Submission(s): 41
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!
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.
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.
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
2
3 2
3 1
2 3
3 3
1 2
2 3
3 1
Sample Output
1 2
2 3
0 0
0 0
0 0
Author
KUT(DPRK)
Source
/* ***********************************************
Author :CKboss
Created Time :2015年08月22日 星期六 10时24分13秒
File Name :HDOJ5409.cpp
************************************************ */ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map> using namespace std; const int maxn=100100; typedef long long int LL;
typedef pair<int,int> pII; struct Edge
{
int from,to,next,id;
}edge[maxn*2]; int Adj[maxn],Size,n,m; void init()
{
Size=0; memset(Adj,-1,sizeof(Adj));
} void Add_Edge(int u,int v,int id)
{
edge[Size].from=u;
edge[Size].id=id;
edge[Size].to=v;
edge[Size].next=Adj[u];
Adj[u]=Size++;
} int Low[maxn],DFN[maxn],Stack[maxn],Belong[maxn];
int Index,top,scc;
bool Instack[maxn],vis[maxn],ve[maxn*2]; void Tarjan(int u,int fa)
{
int v;
Low[u]=DFN[u]=++Index;
Stack[top++]=u;
Instack[u]=true; for(int i=Adj[u];~i;i=edge[i].next)
{
v=edge[i].to;
if(v==fa&&ve[edge[i].id]) continue;
ve[edge[i].id]=true;
if(!DFN[v])
{
Tarjan(v,u);
Low[u]=min(Low[u],Low[v]);
}
else
{
Low[u]=min(Low[u],DFN[v]);
}
}
if(Low[u]==DFN[u])
{
scc++;
do
{
v=Stack[--top];
Belong[v]=scc;
Instack[v]=false;
}while(v!=u);
}
} void scc_solve()
{
memset(DFN,0,sizeof(DFN));
memset(Instack,0,sizeof(Instack)); Index=scc=top=0;
memset(ve,0,sizeof(ve)); for(int i=1;i<=n;i++)
{
if(!DFN[i]) Tarjan(i,i);
}
} int value[maxn];
vector<pII> G[maxn];
int ans[maxn][2];
int bian[maxn][2];
int MX[maxn]; void dfs(int u,int fa)
{
MX[u]=value[u];
for(int i=0,sz=G[u].size();i<sz;i++)
{
int v=G[u][i].first;
if(v==fa) continue;
dfs(v,u);
MX[u]=max(MX[u],MX[v]);
}
} int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout); int T_T;
scanf("%d",&T_T);
while(T_T--)
{
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
bian[i][0]=a; bian[i][1]=b;
Add_Edge(a,b,i); Add_Edge(b,a,i);
}
scc_solve(); /***************REBUILD**********************/ memset(value,0,sizeof(value));
memset(ans,0,sizeof(ans));
int root=0; for(int i=1;i<=n;i++)
{
G[i].clear();
int b=Belong[i];
value[b]=max(value[b],i);
if(value[b]==n) root=b;
} //for(int i=1;i<=scc;i++) cout<<i<<" value: "<<value[i]<<endl; for(int i=0;i<m;i++)
{
int u=Belong[bian[i][0]];
int v=Belong[bian[i][1]];
if(u==v) continue;
G[u].push_back(make_pair(v,i)); G[v].push_back(make_pair(u,i));
} dfs(root,root); //for(int i=1;i<=scc;i++) { cout<<i<<" mx: "<<MX[i]<<endl; } for(int i=0;i<m;i++)
{
int u=Belong[bian[i][0]];
int v=Belong[bian[i][1]];
if(u==v)
{
puts("0 0"); continue;
}
else
{
int mx=min(MX[u],MX[v]);
printf("%d %d\n",mx,mx+1);
}
}
} return 0;
}
最新文章
- 不再为Apache进程淤积、耗尽内存而困扰((转))
- 通俗易懂的 JSon解析处理
- liunux mysql MySQL表名不区分大小写的设置方法
- HDU-统计难题
- IMX6 PCA9698应用层读写库
- N个数全排列的非递归算法
- jquery定位
- python解无忧公主数学题107.py
- SQL表自连接用法
- iOS导航栏-导航栏透明
- VS2008简体中文正式版序列号
- N!水题
- MVC 数据绑定
- Android辅助功能原理与基本使用详解-AccessibilityService
- vue+uwsgi+nginx部署前后端分离项目
- VMware vSphere Client 语言切换
- R中的高效批量处理函数(lapply sapply apply tapply mapply)(转)
- Centos下安装最新版Mono并为windwos服务配置开机启动项
- Vue中methods(方法)、computed(计算属性)、watch(侦听器)的区别
- Redis的核心Hystrix在Spring mvc的使用