10129 - Play on Words

[cs_lyxaa]

Again, I don't know what has happened to my program. I tried all the test cases from board. All seems all right. But I got WA at the judge~~

Code: Select all

#include <cstring>
#include <iostream>
using namespace std;

int visited[26],edges[26][26];

void DFS(int v){
	visited[v]=1;
	for (int w=0;w<26;w++){
		if (edges[v][w]!=0 || edges[w][v]!=0){
				if (v!=w && visited[w]==0) DFS(w);
		}
	}
}

bool isConnected(){
	int cp=0;
	for (int v=0;v<26;v++){
		bool hasDegree=false;
		for (int w=0;w<26;w++){
			if (v==w) continue;
			if (edges[v][w]!=0 || edges[w][v]!=0){
				hasDegree=true;
				break;
			}
		}

		if (hasDegree){
			if (cp==0){
				DFS(v);
				cp++;
			}
			else if (visited[v]==1) {}
			else return false;
		}
	}

	if (cp==1) return true;
	return false;
}

void init(){
	for (int i=0;i<26;i++){
		visited[i]=0;
		for (int j=0;j<26;j++){
			edges[i][j]=0;
		}
	}
}

bool isEuler(){
	if (!isConnected()) return false;

	int err=0,start=0,end=0;
	for (int v=0;v<26;v++){
		if (err) break;

		int inDeg=0,outDeg=0;
		for (int w=0;w<26;w++){
			if (v==w) continue;
			if (edges[v][w]!=0) outDeg+=edges[v][w];
			if (edges[w][v]!=0) inDeg+=edges[w][v];
		}

//		cout << "v=" << v << " inDeg=" << inDeg << " outDeg=" << outDeg << endl;

		switch(inDeg-outDeg){
			case 0: break;
			case 1: 
				end++;
				if (end>1) err=1;
				break;
			case -1: 
				start++;
				if (start>1) err=1;
				break;
			default: err=1;
		}
	}

	if (err) return false;
	else if (start==0 && end==0 || start==1 && end==1) return true;
	else return false;
}

void inputCheck(){
	init();
	int wn;
	char buf[1024];
	cin >> wn;
	for (int i=0;i<wn;i++){
		cin >> buf;
		int v=buf[0]-'a';
		int w=buf[strlen(buf)-1]-'a';
		if (v!=w) {edges[v][w]++;}
	}

	if (isEuler())
		cout << "Ordering is possible." << endl;
	else
		cout << "The door cannot be opened." << endl;
}

int main(){
	int cn; // number of cases
	cin >> cn;
	for (int i=0;i<cn;i++)
		inputCheck();

	return 0;
}

[Jan]

Try the set...

Input:

Code: Select all

1
10
cc
zz
pa
ab
bc
cq
ed
fe
df
qd

Output:

Code: Select all

The door cannot be opened.

Hope it helps.

[przybysz]

What is wrong in my code?

Code: Select all

#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
int main()
{
 int n,m,l=0,t1=0,licz=0,port=1;
 stack<char> s,b;
 string a;    
 cin>>n;
 char t;
 vector<char> v;
 v.push_back(0);
 for(int i=0;i<n;i++)
 {licz=0;
  cin>>m;
  port=1;
  for(int k=0;k<m;k++)
  {
   cin>>a;
   v.push_back(a[0]);
   v.push_back(a.at(a.size()-1));
   a.clear();      
  } 
  s.push(v[2]);l=1;b.push(v[1]);
  vector<int> w(m+1);
  for(int gh=0;gh<=m+1;gh++)
  {w[gh]=0;}
  while(s.size()>0&&port!=m)
  {t=s.top();t1=l;
  for(int r=1;r<w.size();r++){if(w[r]!=1){licz=1;}}
  if(licz==0)break;
   for(int e=1;e<v.size()/2;e++)                 
   {
    if(s.top()==v[2*e+1]&&w[e+1]!=1){port++;w[l]=1;w[e+1]=1;s.push(v[2*e+2]);b.push(v[2*e+1]);l=e+1;}
    else
    {if(b.top()==v[2*e+2]&&w[e+1]!=1){port++;w[l]=1;w[e+1]=1;l=e+1;s.push(v[2*e+2]);}}
   }
   if(t==s.top()&&t1==l)s.pop();               
  }licz=0;
  if(m==1)licz=0;
  else for(int q=1;q<w.size();q++){if(w[q]!=1){licz=1;break;}}
  if(licz==0)cout<<"Ordering is possible."<<endl;
  else cout<<"The door cannot be opened."<<endl;
  while(s.size()>0)s.pop();
  while(b.size()>0)b.pop();
  while(v.size()>1)v.pop_back();
 } 
 return 0;   
}

[forthright48]

Why is this a Euler Path problem? Shouldn't this be a Hamilton Path problem? I need to find a path where I visit each node exactly once, right?

[brianfry713]

No it's a Eulerian Path problem because you have to visit each edge exactly once.