280 - Vertex

[Red Scorpion]

Can anyone tell me what output for this test case:

input:
100
1 2 3 4 5 6 7 8 9 10 11 100 14 44 25 28 0
2 1 4 6 8 9 10 44 25 0
3 2 1 4 6 8 9 33 11 100 0
4 2 1 0
0
10 1 2 3 4 5 6 7 8 9 10
10
1 10 0
0
2 1 2
0

Thanks.

[Per]

My solution outputs:

Code: Select all

83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
83 12 13 15 16 17 18 19 20 21 22 23 24 26 27 29 30 31 32 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
9 1 2 3 4 5 6 7 8 9
10 1 2 3 4 5 6 7 8 9 10

(10 lines)

[Red Scorpion]

Hi, Thanks per.
I got AC.

[Runtime_Error]

why do i got TLE??

[cpp]
#include <iostream.h>
#include <queue>

using std::queue;

void main()
{
int a[110][110], i, j, n, p, q, inNum, nNum, fr;
bool in[110];
while (1) {
cin >> n;
if (n == 0)
break;

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
a[j] = 0;
while (1) {
cin >> p;
if (p == 0)
break;
while (1) {
cin >> q;
if (q == 0)
break;
a[p - 1][q - 1] = 1;
}
}
cin >> nNum;
for (i = 0; i < nNum; i++) {
queue<int> Q;
cin >> p;
inNum = 0;
for (j = 0; j < n; j++)
in[j] = false;

for (j = 0; j < n; j++)
if (a[p - 1][j] == 1)
Q.push(j);

while (!Q.empty()) {
fr = Q.front();
Q.pop();
in[fr] = true;
for (j = 0; j < n; j++)
if (!in[j] && (a[fr][j] == 1))
Q.push(j);
}
for (j = 0; j < n; j++)
if (!in[j])
inNum++;
cout << inNum << ' ';
for (j = 0; j < n; j++)
if (!in[j]) {
cout << j + 1;
if (j != n - 1)
cout << ' ';
}
cout << endl;
}
}
}
[/cpp]

[yaroslavvb]

I'm getting WA using Java, I got correct answer for provided input, and for test cases posted in this board

This is the code:

[java]
import java.io.*;
import java.util.*;

class Main {
public static void main(String argv[]) throws Exception {
Main prog = new Main();
prog.run();
}

public void run() throws Exception {
String line;
while ((line = ReadLn(2550))!=null) {
// read graph:
int vertex_total = Integer.parseInt(line.trim());
if (vertex_total == 0) break;
boolean[][] graph = new boolean[vertex_total][];

// read each vertex spec until hit 0
while (true) {
line = ReadLn(2550);
if ("0".equals(line.trim()))
break;
StringTokenizer str_tok = new StringTokenizer(line);
int vert = Integer.parseInt(str_tok.nextToken())-1;
graph[vert] = new boolean[vertex_total];
initArr(graph[vert]);
try {
while (true) {
int connect = Integer.parseInt(str_tok.nextToken())-1;
if (connect == -1) break;
graph[vert][connect] = true;
}
} catch (NoSuchElementException e) {
System.out.println("Line was "+line);
}
}

// read the query spec
String query = ReadLn(255);
StringTokenizer str_tok = new StringTokenizer(query);
int num_queries = Integer.parseInt(str_tok.nextToken());
for (int i = 0; i < num_queries; ++i) {
int qnode = Integer.parseInt(str_tok.nextToken());
// System.out.println("solving for "+(qnode-1));
solve (graph, qnode-1);
}
}
}

public void solve(boolean[][] graph, int query) {
boolean[] access = new boolean[graph.length];
initArr(access);
access[query] = true;
boolean[] access2 = new boolean[graph.length];
initArr(access2);
for (int stage = 0; stage < access.length; ++stage) {
for (int i = 0; i < access.length; ++i) {
if (!access) continue;
OR(access, graph);
OR(access2, graph);
}
}
printAnswer(access2);
}

public void printAnswer(boolean[] access) {
// count failures
int count = 0;
for (int i = 0; i < access.length; ++i) {
if (access == false)
++count;
}

// print answer
boolean is_first = true;
System.out.print(count+" ");
for (int i = 0; i < access.length; ++i) {
if (access) continue;
if (is_first)
is_first = false;
else
System.out.print(" ");
System.out.print(""+(i+1));
}
System.out.print("\n");
}

public void initArr(boolean[] b) {
for (int i = 0; i < b.length; ++i)
b = false;
}

public void OR(boolean[] b1, boolean[] b2) {
if (b1 == null || b2 == null) return;
for (int i = 0; i < b1.length; ++i)
b1 = b1||b2;
}


static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}
}[/java]

[screagan]

Hi, surely a depth first search of 100 nodes wouldn't time out, so any ideas what I am doing wrong? Am I reading the input from the judge in an incorrect way that causes my program to constantly wait for some non-existent input? I just can't figure it out .

[cpp]

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

streambuf* cinbuf = cin.rdbuf();
streambuf* coutbuf = cout.rdbuf();

void dfs_visit(vector<vector<int> >& G, vector<string>& color, int u)
{
color = "gray";
vector<int>& adj = G;
for (int i=0; i<adj.size(); i++) {
int v = adj;
if (color[v] == "white") {
dfs_visit(G, color, v);
}
}
color = "black";
}

void dfs_sweep(vector<vector<int> >& G, vector<string>& color, vector<int> vertices)
{
fill(color.begin(), color.end(), "white");

for (int i=0; i<vertices.size(); i++) {
int u = vertices;
if (color == "white") {
dfs_visit(G, color, u);
}
}
}

void main()
{
#ifndef ONLINE_JUDGE
ifstream in("Vertex.in");
cin.rdbuf(in.rdbuf());
ofstream out("Vertex.out");
cout.rdbuf(out.rdbuf());
#endif

int n;
cin >> n;
while (true) {
//form the adjacency list
vector<vector<int> > graph(n+1); //n is the number of nodes (numbered consecutively: 1... n)
vector<string> color(n+1);

int node;
while (cin >> node) {
if (node == 0)
break; // no more nodes

int adj_node;
while (cin >> adj_node) {
if (adj_node == 0)
break; //no more adjacent vertices
graph[node].push_back(adj_node);
}
}

int i,j,k;
cin >> j; //number of start nodes to test out
for (i=0; i<j; i++) {
int start;
cin >> start;

//now search the graph starting at "start"
dfs_sweep(graph, color, graph[start]);

//output the results
cout << count(color.begin()+1, color.end(), "white") << " ";
for (k=1; k<color.size(); k++)
if (color[k] == "white")
cout << k << " ";
cout << endl;
}
cin >> n;
if (n == 0) {
break; //no more input
}
}

//restore standard input/output
cin.rdbuf(cinbuf);
cout.rdbuf(coutbuf);
}

[/cpp]

[screagan]

Sorry guys, I just realized I typed the wrong problem number. Of course, it should be 280 not 281. So, does anyone have any idea why I am receiving the time limit error? It is driving me CRAZY because I just can't figure it out. It would be so great if we could actually get some feedback from our submissions.

[IBelieve]

I also get WA but using Pascal
Can you provide some sample test cases for me ?

[neno_uci]

Hello...!!!

I am trying to solve this problem but I always get WA. This is my code:[cpp]
#include <stdio.h>
#define MAX 200

void dfs(int);

int mat[MAX][MAX], tom[MAX], que[MAX], ini, fin, n, t;

int main()
{
scanf("%d", &n);

while (n) {

for (int i = 1; i <= n; i++)
mat[0] = 0;

while (1) {

scanf("%d", &ini);

if (!ini) break;

while (1) {

scanf("%d", &fin);

if (!fin) break;

mat[ini][++mat[ini][0]] = fin;
}

}

scanf("%d", &ini);

for (int i = 0; i < ini; i++)
scanf("%d", &que);

for (int i = 0; i < ini; i++) {

t = n;

for (int j = 1; j <= n; j++)
tom[j] = 0;

dfs(que);

printf("%d", t);

for (int j = 1; j <= n; j++)
if (!tom[j])
printf(" %d", j);

printf("\n");
}

scanf("%d", &n);
}

return 0;
}

void dfs(int inicio)
{
for (int x = 1; x <= mat[inicio][0]; x++)
if (!tom[mat[inicio][x]]) {

tom[mat[inicio][x]] = 1;
dfs(mat[inicio][x]);
t--;
}
}
[/cpp]

Could anyone help me please?
Thanks in advance.
El Neno de la UCI.

[Ferdous]

I can't figure out why I am getting RTE. I spent hours together to find out the fault but failed because of my inefficiency in programming . But I know there are many efficient programmers all over the world who can help me in this regard and I am waiting for help from anyone of you. Please help me. Here's my code:

................Code is deleted later..........

[CDiMa]

I can't figure out why I am getting RTE. I spent hours together to find out the fault but failed because of my inefficiency in programming . But I know there are many efficient programmers all over the world who can help me in this regard and I am waiting for help from anyone of you. Please help me. Here's my code:

Hmmm...
Problem 216 is getting in line, while vertex is problem 280.

If you submit code for problem 280 to the judge for problem 216 you may get in input numbers up to 150. This will pass the bounds for your array and produce an RTE.

If you only mistyped the topic then let me know.

Ciao!!!

Claudio

[Ferdous]

I am extremely sorry for my mistake. I mistyped 216 instead of 280. I sent the code with Problem ID 280 and awarded RTE and still can't figure out what's wrong with my code.

[CDiMa]

I am extremely sorry for my mistake. I mistyped 216 instead of 280. I sent the code with Problem ID 280 and awarded RTE and still can't figure out what's wrong with my code.

The size of the temp array is 100 while a query about 40 nodes will easily overflow that.

Ciao!!!

Claudio

[Ferdous]

Thank u very much. I got AC just increasing the size of temp array to 1000. But I noticed one thing. My code took more than 0:05.00 time. But others solved it within 0:01.00 time. How can I enhance my code or algorithm so that I can get a better solution?

[CDiMa]

Thank u very much. I got AC just increasing the size of temp array to 1000. But I noticed one thing. My code took more than 0:05.00 time. But others solved it within 0:01.00 time. How can I enhance my code or algorithm so that I can get a better solution?

Probably I'm the best on the board to ask this
In your prog you visit the graph for each node queried. This leads to revisit most of the graph each time.
If you avoid it your prog will be faster...

Ciao!!!

Claudio