fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3. class KingdomUnity
  4. { 
  5.     static ArrayList<ArrayList<Integer>> map = new ArrayList<ArrayList<Integer>>();
  6.     static int parent[]=new int[3051];
  7.     static int visited[]=new int[3051];
  8.     static int disc[]=new int[3051];
  9.     static int low[]=new int[3051];
  10.     static int ap[]=new int[3051];
  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.         int T = Integer.parseInt(input.readLine());      
  16.         StringBuilder op = new StringBuilder();
  17.         for(int i=0;i<=3000;i++)
  18.             map.add(new ArrayList<Integer>());
  19.         String[] inLine;
  20.         while(T-->0)
  21.         {
  22.             //Resetting everything!
  23.             Arrays.fill(parent,-1);
  24.             Arrays.fill(visited,-1);
  25.             Arrays.fill(ap,-1);
  26.             Arrays.fill(disc,0);
  27.             Arrays.fill(low,0);
  28.             inLine = input.readLine().split(" ");
  29.             int N = Integer.parseInt(inLine[0]);
  30.             int M = Integer.parseInt(inLine[1]);
  31.             int K = Integer.parseInt(inLine[2]); 
  32.             for(int i=0;i<N;i++)
  33.                 map.get(i).clear();
  34.             //Inputting Graph
  35.             for(int i=0;i<M;i++)
  36.             {
  37.                 inLine = input.readLine().split(" ");
  38.                 int u = Integer.parseInt(inLine[0]);
  39.                 int v = Integer.parseInt(inLine[1]);
  40.                 map.get(u).add(v);
  41.                 map.get(v).add(u);
  42.             }
  43.             time=0;int ans=0;//Reset variable ans and time
  44.             dfs(0);
  45.             for(int i=0;i<N;i++)
  46.                 if(ap[i]==1)ans++;
  47.             ans*=K;    
  48.             op.append(ans).append("\n");
  49.         }
  50.         input.close();
  51.         System.out.println(op);
  52.     }
  53.  
  54.     static void dfs (int u)
  55.     {
  56.         int children=0;
  57.         visited[u]=1;
  58.         disc[u]=low[u]=++time;
  59.         int sz = map.get(u).size();
  60.         for(int i=0;i<sz;i++)
  61.         {
  62.             int v = map.get(u).get(i);
  63.             if(visited[v]==-1)
  64.             {
  65.                 children++;
  66.                 parent[v]=u;
  67.                 dfs(v);
  68.                 // Check if the subtree rooted with v has a connection to one of the ancestors of u
  69.                 low[u]  = Math.min(low[u], low[v]);
  70.                 // u is an articulation point in following cases
  71.                 // (1) u is root of DFS tree and has two or more chilren.
  72.                 if (parent[u] == -1 && children > 1)
  73.                     ap[u]=1;
  74.                 // (2) If u is not root and low value of one of its child is more
  75.                 // than discovery value of u.
  76.                 if (parent[u] != -1 && low[v] >= disc[u])
  77.                     ap[u] = 1;
  78.             }
  79.             else if (v != parent[u])
  80.                 low[u]  = Math.min(low[u], disc[v]);
  81.         }
  82.     }
  83. }
Success #stdin #stdout 0.11s 320320KB
comments ()
stdin
copy 
1
7 6 5
0 1
1 2
3 4
2 4
2 6
5 2
stdout
copy 
15
https://ideone.com/c6dcXY
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!