Hiho: 连通图
2024-10-21 23:21:43
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
还记得上次小Hi和小Ho学校被黑客攻击的事情么，那一次攻击最后造成了学校网络数据的丢失。为了避免再次出现这样的情况，学校决定对校园网络进行重新设计。
学校现在一共拥有N台服务器(编号1..N)以及M条连接，保证了任意两台服务器之间都能够通过连接直接或者间接的数据通讯。
当发生黑客攻击时，学校会立刻切断网络中的一条连接或是立刻关闭一台服务器，使得整个网络被隔离成两个独立的部分。
举个例子，对于以下的网络：
每两个点之间至少有一条路径连通，当切断边(3,4)的时候，可以发现，整个网络被隔离为{1，2，3}，{4，5，6}两个部分：
若关闭服务器3，则整个网络被隔离为{1，2}，{4，5，6}两个部分：
小Hi和小Ho想要知道，在学校的网络中有哪些连接和哪些点被关闭后，能够使得整个网络被隔离为两个部分。
在上面的例子中，满足条件的有边(3,4)，点3和点4。
输入
第1行：2个正整数，N,M。表示点的数量N，边的数量M。1≤N≤20,000, 1≤M≤100,000
第2..M+1行：2个正整数，u,v。表示存在一条边(u,v)，连接了u,v两台服务器。1≤u<v≤N
保证输入所有点之间至少有一条连通路径。
输出
第1行：若干整数，用空格隔开，表示满足要求的服务器编号。从小到大排列。若没有满足要求的点，该行输出Null
第2..k行：每行2个整数，(u,v)表示满足要求的边，u<v。所有边根据u的大小排序，u小的排在前，当u相同时，v小的排在前面。若没有满足要求的边，则不输出
- 样例输入
-
6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6 - 样例输出
-
3 4
3 4import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet; public class Main { static int N_Max=0; //记录根节点是否有两个或多个子树
static int NUM=0; //记录已经遍历的个数
static int [] checktable;
static int [] havechecktable;
static Stack<Integer> stack=new Stack();
public static void main(String[] argv){
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
checktable= new int[N]; //记录遍历顺序
havechecktable= new int[N]; //记录是否已经遍历的标示
int[] y_min= new int[N]; //记录非树边所能达到的小次序值
int[] min = new int[N]; //记录Low值
int[] sort_check = new int[N];//记录每个id点的遍历次序
ArrayList<Integer> [] source = new ArrayList[N]; //记录图的矩阵
ArrayList<Integer> [] blue = new ArrayList[N]; //记录遍历树的矩阵
Set<String> out_xian = new HashSet<String>();
Set<Integer> out_dian = new HashSet<Integer>();
ArrayList<Integer> [] out_xian_2 = new ArrayList[N];
int[][] xian_resource = new int[N][N];
//ArrayList<Integer> out_dian = new ArrayList<Integer>();
//ArrayList out_xian = new ArrayList();
//初始化矩阵
for(int i=0; i<N; i++){
source[i] = new ArrayList<Integer>();
blue[i] = new ArrayList<Integer>();
out_xian_2[i] = new ArrayList<Integer>();
}
/************************记录矩阵**********************/
for(int i=0; i<M; i++){
int x=in.nextInt()-1; int y= in.nextInt()-1;
source[x].add(y);
source[y].add(x);
}
/************************深度遍历**********************/
dfn(source, checktable, blue); /************************验证非树边**********************/
/*
//System.out.println("BLUE: ");
for(int i=0; i<N; i++){ System.out.println(" "+blue[i].toString());
}
*/
/************************get sort_check[](即 dfn[])**********************/
for(int i=0; i<N; i++){
source[i].removeAll(blue[i]);
sort_check[checktable[i]]=i;
}
/************************验证dfn[] and y_min[]**********************/
/*
System.out.println("Sort_Check: ");
for(int i=0; i<N; i++){
System.out.println(" "+sort_check[i]);
}
System.out.println("YELLOW: ");
for(int i=0; i<N; i++){
System.out.println(source[i].toString());
}
*/
/************************Get the y_low[]**********************/
//System.out.println("YELLOW_min: ");
for(int i=0; i<N; i++){
int ymin=i;
for(Object k: source[checktable[i]]){
int spit = sort_check[(int)k];
if(spit<ymin)
ymin=spit;
}
//System.out.print(" "+ymin);
y_min[i]=ymin;
}
/************************Get the low[]**********************/
//System.out.println();
//System.out.println("Low: ");
for(int i=N-1; i>=0; i--){
int k_low = checktable[i];
min[i]=y_min[i];
for(Object o_int : blue[k_low] ){ if(sort_check[k_low]<sort_check[(int)o_int]){ if(min[i]>min[sort_check[(int)o_int]])
min[i]=min[sort_check[(int)o_int]];
}
}
// Low[]
//System.out.println(" "+i+" "+k_low+": "+min[i]);
}
/************************Get result**********************/
for(int i=0; i<N; i++){ for(Object blue_k : blue[i]){ //System.out.println(i+": "+min[sort_check[(int)blue_k]]+">="+sort_check[i]);
if(min[sort_check[(int)blue_k]]>=sort_check[i]){
//System.out.println(i+" added. ");
if(i>0)
out_dian.add(i+1);
if(min[sort_check[(int)blue_k]]>sort_check[i]){
//String temp = "";
int x=i+1;
int y=(int)blue_k+1;
if(i<(int)blue_k){
//temp=x+" "+y;
out_xian_2[i].add((int)blue_k);
}
else{
//temp=y+" "+x;
out_xian_2[(int)blue_k].add(i);
} }
}
}
}
if(N_Max>1)
out_dian.add(1);
//System.out.println(out_dian.toString());
/************************Output result**********************/
java.util.Iterator<Integer> it_dian=out_dian.iterator();
//java.util.Iterator<String> it_xian=out_xian.iterator();
int[] dian_sqit_list = new int[N+1];
String dian_result="";
while(it_dian.hasNext())
{
dian_sqit_list[it_dian.next()]=1;
//dian_result=dian_result+it_dian.next()+" ";
}
for(int i=1; i<=N; i++){
if(dian_sqit_list[i]==1)
dian_result=dian_result+i+" ";
}
//System.out.println("::::::"+dian_result);
if(dian_result.length()>1){
dian_result=dian_result.substring(0,dian_result.length()-1);
System.out.println(dian_result);
}
else
System.out.println("Null"); for(int i=0; i<N; i++){ int[] out_xian_temp = new int[N];
for(int out_m : out_xian_2[i]){ out_xian_temp[out_m]=1; }
for(int j=0; j<N;j++ ){ if(out_xian_temp[j]==1){
System.out.print(i+1);
System.out.print(" ");
System.out.println(j+1);
} } } /*
while(it_xian.hasNext())
{
System.out.println(it_xian.next());
}
*/
} public static void dfn(ArrayList[] source, int[] checktable, ArrayList[] blue){ //int size = source.length;
int start =0;
checktable[NUM++]=start;
havechecktable[start]=1;
stack.push(start);
while(true){ int end = Had(source[start],start,checktable,havechecktable);
if(end>=0){
if(start==0)
N_Max++;
blue[start].add(end);
blue[end].add(start);
//System.out.println(end);
stack.push(end);
//stack.push(start);
//start = end;
//System.out.println("start:"+start+" end"+end+" "+"NUM:"+NUM);
checktable[NUM++]=end;
havechecktable[end]=1;
}
else{ stack.pop();
}
if(stack.isEmpty())
break;
else{
start=stack.pop();
stack.push(start);
} }
//System.out.println(N_Max); } public static int Had(ArrayList s_source, int s_check, int[] check_table, int[] havechecked){ for(int i=0; i<s_source.size();i++){
//System.out.println(s_source.toString());
int key = (int)s_source.get(i);
//System.out.println(key);
if(havechecked[key]==0){
return key;
}
} return -1;
}
}
最新文章
- Knockout.js 组件
- 获取页面内iframe里面的元素
- android自定义拍照
- lua 闭包
- IndexOutOfBoundsException ArrayList 访问越界
- Javascript生成全局唯一标识符（GUID,UUID）的方法
- libcurl
- 第三百零四天 how can I 坚持
- Enterprise Library 服务问题
- SQL Server:OA权限管理设计的实现 下
- python实战--Http代理服务器
- SSO单点登录的实现原理
- 在IOS应用中从竖屏模式强制转换为横屏模式
- 删除iPhone图片，提示“没有删除此项目的权限”
- linux 集群及lvs
- java.util.zip
- java_31 数据表的操作
- 几个例子弄懂JS 的setInterval的运行方式
- JVM调优常用参数
- MapReduce超时原因（Time out after 300 secs）