Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.util.ArrayList;
- import java.util.HashSet;
- import java.util.Scanner;
- // klasa za vrskite vo grafot
- class Edge{
- int color; // 0 = neopredelena, 1 = crvena, 2 = sina
- int vertex1; // indeksot na ednoto teme povrzano so ovaa vrska
- int vertex2; // indeksot na drugoto teme povrzano so ovaa vrska
- Edge(int v1, int v2){
- color = 0;
- vertex1 = v1;
- vertex2 = v2;
- }
- }
- // klasa za teminjata vo grafot
- class Vertex{
- ArrayList<Edge> vrski;
- boolean hasRed; // oznacuva dali sodrzi barem edna crvena vrska
- boolean hasBlue; // oznacuva dali sodrzi barem edna sina vrska
- Vertex(){
- vrski = new ArrayList<>();
- hasRed = hasBlue = false;
- }
- boolean isValid(){
- // vrakja true ako ova teme gi ispolnuva uslovite na zadacata
- return (vrski.size() < 2) || (hasRed && hasBlue);
- }
- }
- public class Main {
- private static void colorEdge(Edge edge, int color, Vertex[] ver){
- // ja boi dadenata vrska, so dadenata boja
- edge.color = color;
- if(color == 1){
- //crvena
- ver[edge.vertex1].hasRed = true;
- ver[edge.vertex2].hasRed = true;
- }
- else{
- //sina
- ver[edge.vertex1].hasBlue = true;
- ver[edge.vertex2].hasBlue = true;
- }
- }
- private static void runDfs(int first, Vertex[] ver){
- int color = 1;
- if(ver[first].hasRed) color = 2;
- int last = first;
- //DFS naogjanje i boenje na pat
- HashSet<Integer> inStack = new HashSet<>();
- while(true){
- inStack.add(last);
- boolean found = false;
- for(Edge e : ver[last].vrski){
- // ako nema boja vrskata, i ako destinacijata ne e vo stack, oboi ja vrskata
- if(e.color == 0){ // proverka za boja na vrskata
- int dest = e.vertex1;
- if(dest == last) dest = e.vertex2;
- if(!inStack.contains(dest)){ // proverka za dali e vo stackot temeto (za da se izbegne ciklus)
- colorEdge(e, color, ver);
- last = dest;
- color = 3 - color; // promena na color, ako e 1 ke stane 2, ako e 2 ke stane 1
- found = true;
- break;
- }
- }
- }
- if(!found){
- break;
- }
- }
- if(first == last){
- //nevozmozno e da se oboi grafot
- //for(Edge e : ver[first].vrski){
- // System.out.println("V1: " + e.color);
- //}
- //System.out.println("YES: " + first);
- System.out.println(0);
- System.exit(0);
- }
- // bidejki znaeme deka site teminja vnatre vo patot go ispolnuvaat uslovot,
- // potrebno e samo da gi proverime pocetnoto teme i krajnoto teme.
- // dokolku ne go ispolnuvaat uslovot, pustame DFS od tie teminja.
- if(!ver[last].isValid()) runDfs(last, ver);
- if(!ver[first].isValid()) runDfs(first, ver);
- }
- public static void main(String[] args){
- Scanner sc = new Scanner(System.in);
- // Scanner sc = null;
- // try {
- // sc = new Scanner(new File("input.IN"));
- // } catch (FileNotFoundException e) {
- // e.printStackTrace();
- // }
- int V = sc.nextInt();
- int E = sc.nextInt();
- //System.out.println("V:" + V);
- // nizi vo koi ke gi cuvame teminjata i vrskite
- Vertex[] ver = new Vertex[V];
- Edge[] edg = new Edge[E];
- for(int i = 0; i < V; i++) ver[i] = new Vertex();
- // citanje input
- for(int i = 0; i < E; i++) {
- int a = sc.nextInt();
- int b = sc.nextInt();
- // pretvoranje vo 0-based counting
- a--;
- b--;
- //kreiranje na vrskata
- edg[i] = new Edge(a, b);
- ver[a].vrski.add(edg[i]);
- ver[b].vrski.add(edg[i]);
- }
- // za sekoe teme za koe ne e ispolnet uslovot na zadacata, ja povikuvame
- // DFS procedurata koja ke najde proizvolen pat koj pocnuva od toa teme
- // i ke go oboi.
- for(int i = 0; i < V; i++){
- if(ver[i].vrski.size() > 2 && !ver[i].isValid()){ // najprvin gi sreduvame teminjata so stepen pogolem od 2, ako takvi ima vo grafot
- //temeto ne go ispolnuva uslovot
- runDfs(i, ver);
- }
- }
- for(int i = 0; i < V; i++){
- if(!ver[i].isValid()){ // sega gi sreduvame ostanatite teminja
- //temeto ne go ispolnuva uslovot
- runDfs(i, ver);
- }
- }
- // pecatenje na shemata za boenje
- StringBuilder sb = new StringBuilder();
- for(int i = 0; i < E; i++){
- int color = edg[i].color;
- if(color == 0){
- // redundantna vrska, moze da bide bilo koja boja, ke ja oboime crvena, bidejki ne e bitno
- color = 1;
- }
- sb.append(color);
- }
- System.out.println(sb);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement