fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. class ArticulationPoints
  4. { 
  5.     static ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>();
  6.     static int parent[]=new int[10100];
  7.     static int visited[]=new int[10100];
  8.     static int disc[]=new int[10100];
  9.     static int low[]=new int[10100];
  10.     static int ap[]=new int[10100];
  11.     static int time=0;
  12.     public static void main(String[]args) throws IOException
  13.     {
  14.         BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
  15.         String inLine[];
  16.         StringBuilder op = new StringBuilder();
  17.         for(int i=0;i<=10100;i++)
  18.             map.add(new ArrayList<Integer>());
  19.         while(true)
  20.         {
  21.             inLine = input.readLine().split(" ");
  22.             int N = Integer.parseInt(inLine[0]);
  23.             int M = Integer.parseInt(inLine[1]);
  24.             if(N==0&&M==0)break;
  25.             //Reset Everything!
  26.             for(int i=0;i<=N;i++)
  27.             { map.get(i).clear();parent[i]=-1;visited[i]=-1;ap[i]=-1;disc[i]=0;low[i]=0;}
  28.             for(int i=0;i<M;i++)
  29.             {
  30.                 inLine = input.readLine().split(" ");
  31.                 int u = Integer.parseInt(inLine[0]);
  32.                 int v = Integer.parseInt(inLine[1]);
  33.                 map.get(u).add(v);
  34.                 map.get(v).add(u);
  35.             }
  36.             time=0;
  37.             dfs(1,true);
  38.             int ans=0;
  39.             for(int i=1;i<=N;i++)
  40.             if(ap[i]==1)ans++;
  41.             op.append(ans).append("\n");
  42.         }
  43.         System.out.println(op);
  44.     }
  45.  
  46.     static void dfs (int u , boolean isRoot)
  47.     {
  48.         int child=0;
  49.         visited[u]=1;
  50.         disc[u]=++time;
  51.         low[u]=disc[u];
  52.         int sz = map.get(u).size();
  53.         for(int i=0;i<sz;i++)
  54.         {
  55.             int v = map.get(u).get(i);
  56.             if(visited[v]!=1)
  57.             {
  58.                 child++;
  59.                 parent[v]=u;
  60.                 dfs(v,false);
  61.                 // Check if the subtree rooted with v has a connection to one of the ancestors of u
  62.                 low[u]  = Math.min(low[u],low[v]);
  63.                 // u is an articulation point in following cases
  64.                 // (1) u is root of DFS tree and has two or more chilren.
  65.                 if (isRoot&& child>=2)
  66.                     ap[u]=1;
  67.                 // (2) If u is not root and low value of one of its child is more
  68.                 // than discovery value of u.
  69.                 if ( !isRoot && low[v] >= disc[u])
  70.                     ap[u]=1;
  71.             }
  72.             else if (v != parent[u])
  73.                 low[u]  = Math.min(low[u], disc[v]);
  74.         }
  75.     }
  76. }
Success #stdin #stdout 0.1s 320320KB
comments ()
stdin
copy 
3 3
1 2
2 3
1 3
6 8
1 3
6 1
6 3
4 1
6 4
5 2
3 2
3 5
0 0
stdout
copy 
0
1
https://ideone.com/R3v8dX
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!