7945. Dwarves

 

Once upon a time, there arose a huge discussion among the dwarves in Dwarfland. The government wanted to introduce an identity card for all inhabitants.

Most dwarves accept to be small, but they do not like to be measured. Therefore, the government allowed them to substitute the field “height” in their personal identity card with a field “relative dwarf size”. For producing the ID cards, the dwarves were being interviewed about their relative sizes. For some reason, the government suspects that at least one of the interviewed dwarves must have lied.

Can you help find out if the provided information proves the existence of at least one lying dwarf?

 

Input. Consists of:

·        One line ith an integer n (1 ≤ n ≤ 105), where n is the number of statements;

·        n lines describing the relations between the dwarves. Each relation is described by one line with “s1 < s2” or “s1 > s2”, telling whether dwarf s1 is smaller or taller than dwarf s2. s1 and s2 are two different dwarf names.

A dwarf name consists of at most 20 letters from “A” to “Z” and “a” to “z”. A dwarf name does not contain spaces. The number of dwarves does not exceed 104.

 

Output. Print “impossible” if the statements are not consistent, otherwise print “possible”.

 

Sample input 1

Sample output 1

3

Dori > Balin

Balin > Kili

Dori < Kili

Impossible

 

 

Sample input 2

Sample output 2

3

Dori > Balin

Balin > Kili

Dori > Kili

Possible

 

 

SOLUTION

graphs - cycles

 

Algorithm analysis

Construct a directed graph, which vertices are the names of the dwarfs. To do this, each name is associated with some integer. For the relation s1 < s2 draw a directed edge from s1 to s2.

The set of the given statements is inconsistent if the constructed graph has cycles. A directed graph contains a cycle if there is an edge running to the gray vertex during depth first search.

 

Example

The graphs given in samples are as follows:

The first graph contains a cycle, so the given relationship between dwarfs is impossible.

Consider the process of creating a graph for the first test case. First appears Dori. Set m[Dori] = 1. Next appears Balin. Set m[Balin] = 2. In the second condition first appears Balin. However, m[Balin] is not 0 (it has already been assigned a number). Then appears Kili. Set m[Kili] = 3.

 

Algorithm realization

Store the directed graph in the adjacency list g. Declare an array used of used vertices in depth first search. The correspondence between the names of the gnomes and the numbers of the vertices is stored in the mapping m (the gnome with the name s corresponds to the vertex number m[s]).

 

vector<vector<int> > g;

vector<int> used;

map<string,int> m;

 

Function dfs implements depth first search from the vertex v.

 

void dfs(int v)

{

  if (flag == 1) return;

  used[v] = 1;

  for(int i = 0; i < g[v].size(); i++)

  {

    int to = g[v][i];

 

The edge (v, to) is currently considered. If it leads to a gray vertex, then a cycle is found, set flag = 1.

 

    if (used[to] == 1)

    {

      flag = 1;

      return;

    }

    if (used[to] == 0) dfs(to);

  }

 

Vertex v becomes black upon completion of processing.

 

  used[v] = 2;

}

 

The main part of the program. Read the number stat of relations between the dwarves. Since the number of dwarfs does not exceed 104, the number of vertices in the graph is not more than 10,000.

 

scanf("%d",&stat);

g.resize(10001); used.resize(10001,0);

 

In the variable n count the number of dwarfs.

 

n = 0;

 

Process stat statements. For each statement construct a directed edge.

 

for(i = 0; i < stat; i++)

{

 

Read a statement s1 < s2 or s1 > s2.

 

  scanf("%s %c %s",s1,&ch,s2);

 

The value m[s] contains the vertex number for dwarf s. If m[s] is not set up yet (m[s] = 0), assign vertex number ++n to dwarf with name s.

 

  if (m[s1] == 0) m[s1] = ++n;

  if (m[s2] == 0) m[s2] = ++n;

 

The relation s1 < s2 for dwarfs means the existence of a directed edge from m[s1] to m[s2].

 

  int from = m[s1], to = m[s2];

  if (ch == '<')

    g[from].push_back(to);

  else

    g[to].push_back(from);

}

 

Run the depth first search on the directed graph. flag = 0 means that graph has no cycles.

 

flag = 0;

for(i = 1; i <= n; i++)

{

  if (!used[i]) dfs(i);

  if (flag == 1) break;

}

 

Depending on the value of the variable flag, print the answer.

 

if (flag == 1) printf("impossible\n"); else printf("possible\n");

 

Java realization

 

import java.util.*;

 

public class Main

{

  static ArrayList<Integer>[] g;

  static HashMap<String, Integer> map = new HashMap<>(); 

  static int used[];

  static int n, flag;

 

  static void dfs(int v)

  {

    if (flag == 1) return;

    used[v] = 1;

    for(int i = 0; i < g[v].size(); i++)

    {

      int to = g[v].get(i);

      if (used[to] == 1)

      {

        flag = 1;

        return;

      }

      if (used[to] == 0) dfs(to);

    }

    used[v] = 2;

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int stat = con.nextInt();

    g = new ArrayList[10001];

    for (int i = 0; i < 10001; i++)

      g[i] = new ArrayList<Integer>();

   

    n = 0;   

    for(int i = 0; i < stat; i++)

    {

      String s1 = con.next();

      char ch = con.next().charAt(0);

      String s2 = con.next();

      if (!map.containsKey(s1)) map.put(s1, ++n);

      if (!map.containsKey(s2)) map.put(s2, ++n);

     

      Integer from = map.get(s1), to = map.get(s2);

      if (ch == '<')

        g[from].add(to);

      else

        g[to].add(from);

    }

   

    used = new int[n+1];

    flag = 0;

    for(int i = 1; i <= n; i++)

    {

      if (used[i] == 0) dfs(i);

      if (flag == 1) break;

    }

 

    if (flag == 1) System.out.println("impossible");

    else System.out.println("possible");

  }

}