https://www.adonaimedrado.pro.br/wiki/index.php?action=history&feed=atom&title=Solu%C3%A7%C3%A3o%3A_Problema_do_grafo_conexo_%28Thiago_Freire%29 2026-05-27T05:40:21Z Revision history for this page on the wiki MediaWiki 1.26.2 https://www.adonaimedrado.pro.br/wiki/index.php?title=Solu%C3%A7%C3%A3o:_Problema_do_grafo_conexo_(Thiago_Freire)&diff=2961&oldid=prev 2009-05-27T05:37:55Z

<p>New page: &lt;code lang=&quot;java&quot;&gt; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashMap; import java.util.Hash...</p> <p><b>New page</b></p><div>&lt;code lang=&quot;java&quot;&gt;<br /> <br /> import java.io.BufferedReader;<br /> import java.io.IOException;<br /> import java.io.InputStreamReader;<br /> import java.util.ArrayList;<br /> import java.util.HashMap;<br /> import java.util.HashSet;<br /> <br /> public class Graph {<br /> <br /> private HashMap&lt;Integer, ArrayList&lt;Integer&gt;&gt; adj = new HashMap&lt;Integer, ArrayList&lt;Integer&gt;&gt;();<br /> <br /> private void addVertex(int v) {<br /> adj.put(new Integer(v), new ArrayList&lt;Integer&gt;());<br /> }<br /> <br /> private void removeVertex(int v) {<br /> adj.remove(v);<br /> }<br /> <br /> private Integer getFirstVertex() {<br /> return adj.keySet().iterator().next();<br /> }<br /> <br /> private void addEdge(int u, int v) {<br /> if (!adj.containsKey(u)) <br /> addVertex(u);<br /> if (!adj.containsKey(v)) <br /> addVertex(v);<br /> adj.get(u).add(v);<br /> adj.get(v).add(u);<br /> }<br /> <br /> private boolean hasNeighbors(int v) {<br /> return !adj.get(v).isEmpty();<br /> }<br /> <br /> private int getFirstNeighbor(int v) {<br /> return adj.get(v).get(0);<br /> }<br /> <br /> private void removeFirstNeighbor(int v) {<br /> adj.get(v).remove(0);<br /> }<br /> <br /> private int isConnected() {<br /> HashSet&lt;Integer&gt; possibleKeys = new HashSet&lt;Integer&gt;();<br /> HashSet&lt;Integer&gt; keys = new HashSet&lt;Integer&gt;();<br /> int v;<br /> <br /> possibleKeys.add(getFirstVertex());<br /> while (!possibleKeys.isEmpty()) {<br /> v = possibleKeys.iterator().next();<br /> keys.add(v);<br /> while (hasNeighbors(v)) {<br /> if (!keys.contains(getFirstNeighbor(v)))<br /> possibleKeys.add(getFirstNeighbor(v));<br /> removeFirstNeighbor(v);<br /> }<br /> removeVertex(v);<br /> possibleKeys.remove(v);<br /> }<br /> <br /> return adj.isEmpty() ? 1 : 0;<br /> }<br /> <br /> public static void main(String[] args) throws IOException {<br /> Graph g = new Graph();<br /> BufferedReader br = new BufferedReader(new InputStreamReader(System.in));<br /> String[] vertices;<br /> <br /> int n = Integer.parseInt(br.readLine());<br /> for (int i = 0; i &lt; n; i++) {<br /> vertices = br.readLine().split(&quot; &quot;);<br /> g.addEdge(Integer.parseInt(vertices[0]), Integer.parseInt(vertices[1]));<br /> }<br /> System.out.println(g.isConnected());<br /> }<br /> }<br /> <br /> &lt;/code&gt;</div>

189.105.130.222