I did get AC on this. I used queue and in_degree array. First pushed zero in_degree elements in queue and then visited neighbour for each element in front , reduced in_degree of neighbours by 1 each time to indicate one parent has reduced. Edited by author 29.04.2020 12:08 What is test case 1? It's the same as the given sample input. But what if i have the same answer that in sample, and get WA1? Help! I dont understand that problem. test: 3 0 1 0 0 can you explain which one is right ? 2 1 3 or 3 2 1 In addition I get WA6 and this is my code : /* #include <stdio.h> #define maxn 105 int vp[maxn], pv[maxn]; int main() {
int n, x, y; scanf("%d", &n); for(int i = 1; i <= n; i ++) { vp[i] = i; pv[i] = i; } for (int i = 1; i <= n; i ++) { int min = vp[i]; while(1) { scanf("%d", &x); if(x == 0) break; if(vp[x] < min) min = vp[x]; } for (int j = i - 1; j >= min; j --) { pv[j + 1] = pv[j]; vp[pv[j + 1]] = j + 1; } pv[min] = i; vp[i] = min; } for (int i = 1; i <= n; i ++) { printf("%d ", pv[i]); } return 0; } */ I don't understand what your code does. Probably intended solution uses an algorithm calling "topological sorting". (My solution uses it too). By definition, topological sorting solves the task 1022. Edited by author 14.07.2017 12:44 Yeah you are right. It is not an algorithm. It is just an idea but i think this idea should accept! Yes, I made a mistake. Correct would be something like. Intended solution is a program that calculates topological sort of vertices of a graph built from input data using some well-known algorithm for calculating topological sorting In topological sorting, you are doing depth first search and memorize vertices when you leave them. When all the vertices are considered, you have memorized vertices in reversed topological sorted order. Edited by author 14.07.2017 12:45 void dfs(int nd) { for(int to : adj[nd]) if(!used[to]) dfs(to); used[nd] = true; //switch the node into visited ans.push_back(nd); //put the node to array } Edited by author 19.09.2017 16:03 My AC program gives "3 2 1". So, probably "3 2 1" is the right answer. If several sequences satisfy the conditions of the problem, you are to write to the standard output any of them!!! ;) ;/ You should all do just DFS!(How? Just enter any node and check its adjacents were visited. So that enter node which was not visited before. Finally, put this node to array after checking and reverse the answer array)! Edited by author 19.09.2017 16:04 I got WA#1 :( What's wrong bros? =============================================================== static int speakerCount = 0; static void solve() throws IOException { final int N = nextInt(); // graph[i][j] = true: i-th is parent of j-th final boolean[][] graph = new boolean[N + 1][N + 1]; for (int line = 1; line <= N; line++) { int parent = nextInt(); if (parent == 0) { continue; } int child = nextInt(); while (0 < child) { graph[parent][child] = true; child = nextInt(); } } StringBuilder speakerList = new StringBuilder(); final boolean[] visitedNodes = new boolean[N + 1]; while (speakerCount < N) { for (int node = 1; node <= N; node++) { if (!visitedNodes[node]) { visit(node, visitedNodes, speakerList, graph); break; } } } out.println(speakerList.toString().trim()); } private static void visit(int node, boolean[] visitedNodes, StringBuilder speakerList, boolean[][] graph) { // Stop if marked if (visitedNodes[node]) { return; } // Marked visitedNodes[node] = true; // Visit each child for (int child = 1; child < visitedNodes.length; child++) { if (graph[node][child]) { visit(child, visitedNodes, speakerList, graph); } } speakerList.insert(0, node + " "); speakerCount++; } Edited by author 23.05.2014 15:48 I think the problem is that a children could have more than 1 parent - and here you have to check if all of his parents have been printed. If you can't find the solution yourself - write and I will tell you a way. P.S. Other people say that "One of the lines in test 4 has trailing space. This old problem was designed for Pascal/C++, such inputs treated as a bad style nowadays." I don't know what this means, but first check if this is the problem! Edited by author 07.01.2015 04:12 THIS IS ACCEPTED CODE // *CoDeD by Ye.A # include <iostream> # include <cstdlib> # include <cstdio> # include <vector> # include <algorithm> using namespace std; const int N = 222; vector <int> g[N], ans; int n; bool used[N]; int main () { //freopen ("input.txt", "r", stdin); //freopen ("output.txt", "w", stdout); scanf ("%d", &n); for (int i = 1; i <= n; i++) while (1) { int x; scanf ("%d", &x); if (!x) break; g[x].push_back (i); }
while (ans.size() != n) for (int i = 1; i <= n; i++) if (!used[i] && g[i].empty()) { ans.push_back (i); used[i] = true; for (int j = 1; j <= n; j++) if (binary_search(g[j].begin(), g[j].end(), i)) g[j].erase (lower_bound(g[j].begin(), g[j].end(), i)); }
for (int i = 0; i < n; i++) printf ("%d ", ans[i]);
return 0; } I am using priority queue. Priority is determined by the number of elements. The top element is one without parents. When it's removed from the queue, it's being deleted as a parent from all the other elements. I get WA#4. Any idea why? This is my code. Can someone tell me why do I get WA#4? import java.util.Collection; import java.util.Comparator; import java.util.HashSet; import java.util.Hashtable; import java.util.Iterator; import java.util.PriorityQueue; import java.util.Scanner; public class MartianCouncil { public static void main(String[] args) { Hashtable<Integer, TreeNode> global = new Hashtable<Integer, TreeNode>(); Scanner s = new Scanner(System.in); int n = s.nextInt(); if (n == 0) { s.close(); return; } s.nextLine(); for (int i = 1; i <= n; i++) { TreeNode node = global.get(i); if (node == null) { node = new TreeNode(i); global.put(i, node); } String line = s.nextLine(); String[] nums = line.split(" "); for (int j = 0; j < nums.length - 1; j++) { int num = Integer.parseInt(nums[j]); TreeNode nd = global.get(num); if (nd == null) { nd = new TreeNode(num); global.put(num, nd); } node.addChild(nd); } } s.close(); print(global); }
public static void print(Hashtable<Integer, TreeNode> global) { PriorityQueue<TreeNode> q = new PriorityQueue<TreeNode>(); q.addAll(global.values()); StringBuilder res = new StringBuilder(""); while (!q.isEmpty()) { TreeNode nd = q.poll(); res = res.append((res.length() == 0) ? "" : " "); res = res.append(nd.getNum()); } System.out.print(res); }
public static class TreeNode implements Comparable<MartianCouncil.TreeNode> {
private int num = 0; private Collection<MartianCouncil.TreeNode> children = new HashSet<MartianCouncil.TreeNode>(); private Collection<MartianCouncil.TreeNode> parents = new HashSet<MartianCouncil.TreeNode>();
public TreeNode(int num) { this.num = num; }
public int hashCode() { return num; }
public boolean equals(Object o) { if (o == null) { return false; } else if (!(o instanceof MartianCouncil.TreeNode)) { return false; } else { return (this.hashCode() == o.hashCode()); } }
public boolean addChild(MartianCouncil.TreeNode child) { child.parents.add(this); return children.add(child); }
public boolean removeChild(MartianCouncil.TreeNode child) { child.parents.remove(this); return children.remove(child); }
public boolean addParent(TreeNode parent) { parent.children.add(this); return parents.add(parent); }
public boolean removeParent(TreeNode parent) { parent.children.remove(this); return parents.remove(parent); }
public void removeAllChildren() { Iterator<TreeNode> it = children.iterator(); while (it.hasNext()) { TreeNode child = it.next(); child.parents.remove(this); } children.clear(); }
public int getNum() { return num; }
public Collection<TreeNode> getChildren() { return children; }
public int getParentsNum() { return parents.size(); } @Override public int compareTo(MartianCouncil.TreeNode nd) { return Math.round(Math.signum(this.getParentsNum() - nd.getParentsNum())); } }
public class TreeNodeComp implements Comparator<MartianCouncil.TreeNode> { @Override public int compare(MartianCouncil.TreeNode nd1, MartianCouncil.TreeNode nd2) { return Math.round(Math.signum(nd1.getParentsNum() - nd2.getParentsNum())); } }
} quite difficult problem to solve without knowing dfs :) Edited by author 21.10.2013 13:32 DFS the graph, the earlier leave the vertex,the later it shows in the array DFS doesn't work here.. It's work. Topological sorting this graph(whith dfs), and write answer Edited by author 26.07.2010 15:12 One of the lines in test 4 has trailing space. This old problem was designed for Pascal/C++, such inputs treated as a bad style nowadays. Thanks for info. I have changed something in my program now not to "look" on any unnecessary spaces. Thanks for the info. You've saved my time :) This is my ac code: #include<iostream> #include<queue> #include<cstdio> using namespace std; bool a[100][100]; queue <int> l,s; int p,u[100],n,fr,o=0; int main() { scanf("%d",&n); for(int i=0;i<n;i++) { u[i]=0; for(int j=0;j<n;j++) a[i][j]=false; } for(int i=0;i<n;i++) { p=1; while(1==1) { scanf("%d",&p); if(p==0) break; a[i][p-1]=true; u[p-1]++; } } for(int i=0;i<n;i++) if(u[i]==0) s.push(i); while(!s.empty()) { o++; fr=s.front(); s.pop(); for(int i=0;i<n;i++) if(a[fr][i]) { u[i]--; if(u[i]==0) s.push(i); } printf("%d",fr+1); if(o!=n) printf(" "); } printf("\n"); return 0; } Hey Probably because N <= 100 :-D package topological_sorting; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.LinkedList; import java.util.StringTokenizer; public class Main { public static BufferedReader in; public static PrintWriter out; public static LinkedList<Integer> L; // list of ordered nodes public static LinkedList<Integer> S;// list of nodes which doesn't have // unvisited parent public static void main(String args[]) throws IOException { L = new LinkedList<Integer>(); S = new LinkedList<Integer>(); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); // input // source int size = (int) Integer.parseInt(in.readLine());// number of members in // meeting int a[][] = new int[size][size];// view.row-numeration of // members.column-whether certain row // has member as child int b[][] = new int[size][size];// view2.it is as // view.column-node.rows-nodes as parent // of column node read(a, in, size);// fill view fillView2(a, b); setNodes(b); // nodes without incoming edges while (S.size() != 0) { int node = (int) S.remove(); L.add(node); for(int j=0;j<a[node-1].length;j++){ if(a[node-1][j]==0){ break; }else{ int childNode = a[node-1][j]; b[node-1][childNode-1]=0; if(!hasParent(b,childNode)){ S.add(childNode); } } } } showList(L); } private static boolean hasParent(int b[][],int node){ boolean hasParent = false; for(int i=0;i<b.length;i++){ if(b[i][node-1]!=0){ hasParent=true; break; } } return hasParent; } private static void showList(LinkedList<Integer> l2) { for (int i = 0; i < l2.size(); i++) { System.out.print(l2.get(i) + " "); } System.out.println(); } private static void setNodes(int[][] b) { for (int j = 0; j < b[0].length; j++) { for (int i = 0; i < b.length; i++) { if (b[i][j] == 0) { if (i == b.length - 1) { S.add(j + 1); } } else { break; } } } } private static void fillView2(int[][] a, int[][] b) { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (a[i][j] == 0) { break; } else { b[i][a[i][j] - 1] = 1; } } } } // fill view with data private static void read(int[][] a, BufferedReader in, int size) throws IOException { int iterator = 0; while (iterator < size) { StringTokenizer tokenizer = new StringTokenizer(in.readLine()); int j = 0; while (tokenizer.hasMoreTokens()) { a[iterator][j] = (int) Integer.parseInt(tokenizer.nextToken()); j++; } iterator++; } } // observe view public static void showArray(int a[][]) { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { System.out.print(a[i][j] + " "); } System.out.println(); } } } Is someone know input for the 4-th test? (My programm had crash) Is it possible to determine inputs? Are there exist resource&? In the 4-th test I have problem time limit exception. 5 0 4 5 1 0 1 0 5 3 0 3 0 Why output is: 2 4 5 3 1 not: 2 4 3 5 1 and i can't understand the WA in test#4 please explain me chunki 3 5ni farzandi Edited by author 08.07.2011 16:39 Как произвести считывания на java. Here's my solution : - Input & reverse all the edges - DFS from all vertexs - If depth = N then output in reverse order What's wrong w/ this one ???? the graph may be not connected. I was WA#2 and now I get Ac, because: Graph can be not connected I got WA#2 too, but I thought that the graph is supposed to be not connected. Can help me identify my errors , here's my solution : - I reverse all the edges - DFS from the vertex without any other vertex pointing to - Count the depth, if depth = number of vertex -> output in reverse order 3Q,i made the same mistake,and i now get AC 1888582 05:04:16 29 ноя 2007 Snetch 1022 Pascal Accepted 0.015 179 КБ 2170208 13:57:22 23 июл 2008 Mansurov Artur 1022 C++ Accepted 0.001 153 КБ O(n^2) simple search Can you send me your O(n^2) solution?I got AC with O(n^3) my mail is:keivan.alizadeh@gmail.com |
|