315 - Network

[richatibrewal]

Accepted

[brianfry713]

A line may be longer than 100 chars, 1000 is enough.

[richatibrewal]

Still getting WA...

[brianfry713]

Change:
char s[MAXLEN]
to:
char s[1000]

Change:
fgets(s,100,stdin);
to:
fgets(s,1000,stdin);

And your code will get AC.

[richatibrewal]

Thanx brianfry713.

[brianfry713]

Input:

Code: Select all

4
1 4 2 3
2 4
0
3
2 1 3
0
0

AC output:

Code: Select all

1
1

[mratan16]

Hi, I've been trying to solve 315-Networks but seem to keep getting WA

Also I can't seem to understand why it fails on some sample cases here.

Thanks in advance.

Code: Select all

#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <sstream>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <deque>
#include <stdio.h>
#define UNVISITED -1

using namespace std;


int dfs_root,rootchild;

vector<vector<int> >AdjList; 
int dfs_num[101], dfs_low[101], parent[101];
bool articulation_point[101];
int dfs_counter,counter;

void GetArtic(int u) 
{
  dfs_low[u]=dfs_num[u]=dfs_counter++;

  for(int i=0; i<AdjList[u].size(); ++i)
  {
    int cur=AdjList[u][i];
    if(dfs_num[cur]==UNVISITED)
    {
      parent[cur]=u; 
      if(u==dfs_root){ 
        rootchild++; 
      }
    
      GetArtic(cur);

      if(dfs_low[cur]>=dfs_num[u]){ 
        articulation_point[u]=true;
      }
      dfs_low[u]=min(dfs_low[u],dfs_low[cur]);
    }
    else if(dfs_num[cur]<dfs_low[u]){
      dfs_low[u]=min(dfs_low[u], dfs_num[cur]);
    }
  }
}



int main()
{
  int N; 
  while(cin >> N && N)
  {
    AdjList.clear(); 
    AdjList.assign(101,vector<int>());

    for(int i=0; i<=100; ++i){
      articulation_point[i]=false;
      dfs_num[i]=UNVISITED;
    }

    string input; 
    while(getline(cin,input) && input!="0")
    {
      bool first=true;
      int p1,p2; 
      for(int i=0; i<input.size(); ++i)
      {
        if(input[i]!=' '){
          if(first){
            p1=input[i]-'0';
            first=false;
          }else if(!first){
            p2=input[i]-'0';
            AdjList[p1].push_back(p2);
            AdjList[p2].push_back(p1);
          }
        }
      }
    }
    counter=0;
    dfs_counter=1;
    for(int i=0; i<=N; ++i)
    {
      if(dfs_num[i]==UNVISITED){
        dfs_root=i,rootchild=0; 
        GetArtic(i);
        articulation_point[i]=(rootchild>1);
      }
    }
    for(int i=0; i<=N; ++i){
      if(articulation_point[i]){
        cout << "artic at: " <<i << endl;
        counter++;
      }
    }

    cout << counter << endl;

  }
}

[milesstevenson]

Hi. I'm getting Runtime Error for some odd reason. I pass many testcases. Can someone help me point out why I am getting this error? Is it an issue with the format of the problem or my code? Many thanks.

Code: Select all

import java.util.Arrays;
import java.util.ArrayList;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Miles Stevenson
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task315 solver = new Task315();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task315 {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int u, v, N, count;
        String line;
        while ((N = in.nextInt()) != 0) {
            count = 0;
            Graph G = new Graph(N);
            while ((line = in.nextLine()).charAt(0) != '0') {
                u = line.charAt(0) - '0';
                for (int i = 2; i < line.length(); i += 2) {
                    v = line.charAt(i) - '0';
                    G.addEdge(u, v);
                }
            }
            Biconnected bic = new Biconnected(G);
            for (int i = 0; i < N; i++)
                if (bic.isArticulation(i))
                    count++;
            out.println(count);
        }
    }
}

class Graph {
    private int V;
    private int E;
    private ArrayList<Integer>[] adj;

    Graph(int V) {
        this.V = V;
        E = 0;
        adj = new ArrayList[V];
        for (int v = 0; v < V; v++)
            adj[v] = new ArrayList<Integer>();
    }

    public void addEdge(int v, int w) {
        adj[v-1].add(w-1);
        adj[w-1].add(v-1);
        E++;
    }

    public int V() { return V; }

    public Iterable<Integer> adj(int v) { return adj[v]; }
}

class Biconnected {
    private int[] pre;
    private int[] low;
    private int cnt;
    private boolean[] articulation;

    Biconnected(Graph G) {
        pre = new int[G.V()];
        low = new int[G.V()];
        articulation = new boolean[G.V()];
        cnt = 0;

        Arrays.fill(pre, -1);
        Arrays.fill(low, -1);

        for (int v = 0; v < G.V(); v++)
            if (pre[v] == -1)
                dfs(G,v,v);
    }

    public void dfs(Graph G, int u, int v) {
        int children = 0;
        pre[v] = cnt++;
        low[v] = pre[v];

        for (int w : G.adj(v)) {
            if (pre[w] == -1) {
                children++;
                dfs(G, v, w);

                low[v] = Math.min(low[v], low[w]);

                if (low[w] >= pre[v] && u != v)
                    articulation[v] = true;
            }
            else if (w != u)
                low[v] = Math.min(low[v], pre[w]);
        }
        if (u == v && children > 1)
            articulation[v] = true;
    }

    public boolean isArticulation(int v) { return articulation[v]; }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(nextLine());
            }
            return tokenizer.nextToken();
        } catch (NullPointerException e) {
            return null;
        }
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}

[arbolsaa]

Hi, i'm getting WA for some odd reason. I pass many testcases. Can someone help me point out why I am getting this? Is it an issue with the format of the problem or my code? Many thanks.

Code: Select all

import java.awt.event.AdjustmentListener;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Vector;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N;
		while ((N = Integer.parseInt(in.readLine())) != 0) {
			// System.out.println("Hola mundo");
			boolean[][] matrix = new boolean[N][N];
			String[] line;
			int pivot;

			while ((pivot = Integer
					.parseInt((line = in.readLine().split(" "))[0])) != 0) {
				pivot--;
				for (int i = 1; i < line.length; i++) {
					int target = Integer.parseInt(line[i]) - 1;
					matrix[pivot][target] = true;
					matrix[target][pivot] = true;
				}

			}
			initArticulationPointBridge(N);
			for (int i = 0; i < N; i++) {
				if (dfs_num.get(i) == DFS_WHITE) {
					dfsRoot = i;
					rootChildren = 0;
					articulationPontAndBridge(i, matrix);
					articulationVertex.set(dfsRoot, rootChildren > 1);
				}
			}
			int count = 0;
			for (int i = 0; i < N; i++) {
				if (articulationVertex.get(i)) {
					count++;
				}
			}
			sb.append(count + "\n");
		}
		sb.deleteCharAt(sb.length() - 1);
		System.out.println(sb.toString());
		in.close();
		System.exit(0);

	}

	private static void initArticulationPointBridge(int N) {
		initGraphCheck(N);
		dfs_low = new Vector<Integer>();
		dfs_low.addAll(Collections.nCopies(N, 0));
		articulationVertex = new Vector<Boolean>();
		articulationVertex.addAll(Collections.nCopies(N, false));
		dfsNumberCounter = 0;
	}

	private static void initGraphCheck(int N) {
		initDFS(N);
		dfs_parent = new Vector<Integer>();
		dfs_parent.addAll(Collections.nCopies(N, 0));
	}

	private static void initDFS(int N) {
		dfs_num = new Vector<Integer>();
		dfs_num.addAll(Collections.nCopies(N, DFS_WHITE));

	}

	private static Vector<Integer> dfs_low, dfs_num, dfs_parent;
	private static int dfsNumberCounter, rootChildren, dfsRoot;
	private static Integer DFS_WHITE = -1;
	private static Vector<Boolean> articulationVertex;

	private static void articulationPontAndBridge(int u, boolean[][] matrix) {
		dfs_low.set(u, dfsNumberCounter);
		dfs_num.set(u, dfsNumberCounter++);
		boolean[] adjList = matrix[u];
		for (int i = 0; i < adjList.length; i++) {
			if (adjList[i]) {
				if (dfs_num.get(i) == DFS_WHITE) {
					dfs_parent.set(i, u);
					if (u == dfsRoot) {
						rootChildren++;
					}
					articulationPontAndBridge(i, matrix);
					if (dfs_low.get(i) > dfs_num.get(u)) {
						articulationVertex.set(u, true);
					}
					dfs_low.set(u, Math.min(dfs_low.get(u), dfs_low.get(i)));
				} else if (i != dfs_parent.get(u)) {
					dfs_low.set(u, Math.min(dfs_low.get(u), dfs_num.get(i)));
				}
			}
		}
	}

}