「1144 Network」の編集履歴(バックアップ)一覧はこちら
「1144 Network」(2006/05/13 (土) 23:55:30) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**1144 Network
**解答例
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
int n = (new Scanner(sc.nextLine())).nextInt();
if(n==0) break;
boolean a[][] = new boolean[n][n];
for(int i=0;i<n;i++) Arrays.fill(a[i], false);
while(true){
Scanner scline = new Scanner(sc.nextLine());
int u = scline.nextInt()-1;
if(u==-1) break;
while(scline.hasNext()){
int v = scline.nextInt()-1;
a[u][v] = true;
a[v][u] = true;
}
}
Solver sol = new Solver(n, a);
System.out.println(sol.solve());
}
}
}
class Solver{
int n;
boolean a[][];
int dfcnt;
boolean[] searched;
int[] dfnumber;
int[] low;
int[] prev;
public Solver(int n, boolean[][] a) {
this.n = n;
this.a = a;
dfcnt = 0;
searched = new boolean[n];
Arrays.fill(searched, false);
dfnumber = new int[n];
low = new int[n];
prev = new int[n];
}
private void dfs(){
prev[0] = -1;
dfs(0);
}
private void dfs(int u){
searched[u] = true;
dfnumber[u] = dfcnt;
dfcnt++;
low[u] = dfnumber[u];
for(int i=0;i<n;i++){
if(u==i) continue;
if(a[u][i]&&searched[i]){
low[u] = Math.min(dfnumber[i], low[u]);
}
}
for(int i=0;i<n;i++){
if(u==i) continue;
if(a[u][i]&&!searched[i]){
prev[i] = u;
dfs(i);
low[u] = Math.min(low[i], low[u]);
}
}
}
public int solve(){
dfs();
int cnt = 0;
// root
int rootdeg = 0;
for(int i=0;i<n;i++){
if(prev[i]==0){
rootdeg++;
}
}
if(rootdeg>=2) cnt++;
// except root
for(int i=1;i<n;i++){
boolean flag = false;
for(int j=0;j<n;j++){
if(prev[j]==i){
if(low[j]>=dfnumber[i]){
flag = true;
break;
}
}
}
if(flag) cnt++;
}
return cnt;
}
}
**1144 Network
**解答方針
関節点の個数を数える問題.アルゴリズムについてはグラフ理論の教科書に譲る.
**解答例
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true){
int n = (new Scanner(sc.nextLine())).nextInt();
if(n==0) break;
boolean a[][] = new boolean[n][n];
for(int i=0;i<n;i++) Arrays.fill(a[i], false);
while(true){
Scanner scline = new Scanner(sc.nextLine());
int u = scline.nextInt()-1;
if(u==-1) break;
while(scline.hasNext()){
int v = scline.nextInt()-1;
a[u][v] = true;
a[v][u] = true;
}
}
Solver sol = new Solver(n, a);
System.out.println(sol.solve());
}
}
}
class Solver{
int n;
boolean a[][];
int dfcnt;
boolean[] searched;
int[] dfnumber;
int[] low;
int[] prev;
public Solver(int n, boolean[][] a) {
this.n = n;
this.a = a;
dfcnt = 0;
searched = new boolean[n];
Arrays.fill(searched, false);
dfnumber = new int[n];
low = new int[n];
prev = new int[n];
}
private void dfs(){
prev[0] = -1;
dfs(0);
}
private void dfs(int u){
searched[u] = true;
dfnumber[u] = dfcnt;
dfcnt++;
low[u] = dfnumber[u];
for(int i=0;i<n;i++){
if(u==i) continue;
if(a[u][i]&&searched[i]){
low[u] = Math.min(dfnumber[i], low[u]);
}
}
for(int i=0;i<n;i++){
if(u==i) continue;
if(a[u][i]&&!searched[i]){
prev[i] = u;
dfs(i);
low[u] = Math.min(low[i], low[u]);
}
}
}
public int solve(){
dfs();
int cnt = 0;
// root
int rootdeg = 0;
for(int i=0;i<n;i++){
if(prev[i]==0){
rootdeg++;
}
}
if(rootdeg>=2) cnt++;
// except root
for(int i=1;i<n;i++){
boolean flag = false;
for(int j=0;j<n;j++){
if(prev[j]==i){
if(low[j]>=dfnumber[i]){
flag = true;
break;
}
}
}
if(flag) cnt++;
}
return cnt;
}
}