AC - Construct a Palindrome

Author: Kevin Sheng

Edit This Page

Table of Contents

ExplanationImplementation

Official Analysis

Explanation

While the official editorial starts from the beginning and end of the graph and tries to work its way to a common node or edge, it's also possible to start from the common location and try to get to the beginning and end.

Implementation

Time Complexity: O(N2+M)\mathcal{O}(N^2 + M)

C++

#include <iostream>
#include <queue>
#include <vector>


using std::cout;
using std::endl;
using std::pair;
using std::vector;


int main() {

Java

import java.io.*;
import java.util.*;


public class Main {
 	Code Snippet: Edge Class (Click to expand)


	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int nodeNum = Integer.parseInt(initial.nextToken());

Python

from collections import deque


node_num, edge_num = [int(i) for i in input().split()]
neighbors = [[] for _ in range(node_num)]
for _ in range(edge_num):
	n1, n2, c = input().split()
	n1 = int(n1) - 1
	n2 = int(n2) - 1
	neighbors[n1].append((n2, c))
	neighbors[n2].append((n1, c))

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum