hihoCoder week 51-1-欧拉路·三

hihoCoder week 51-1-欧拉路·三

——By 无名的冒险者

3

00010111

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxN = 16;
int edge[1 << kMaxN][2];
int path[1 << kMaxN];
int path_size = 0;
int n;
void MakeGraph()
{
memset(edge, -1, sizeof(edge));
int nn = 1 << (n - 1);
for (int i = 0; i < nn; i++)
{
edge[i][0] = (i << 1)&(nn - 1);
edge[i][1] = edge[i][0] + 1;
}
}
void DFS(int p)
{
for (int i = 0; i < 2; i++)
{
int q = edge[p][i];
if (q != -1)
{
edge[p][i] = -1;
DFS(q);
}
}
path[path_size++] = p;
}
int main()
{
scanf("%d", &n);
if (n == 1)
{
printf("01");
return 0;
}
else if (n == 2)
{
printf("1100");
return 0;
}
MakeGraph();
DFS(0);
while (--path_size)
printf("%d", path[path_size] & 1);
return 0;
}


hihoCoder week 50-1-欧拉路·二

hihoCoder week 50-1-欧拉路·二

——By 无名的冒险者

5 5
3 5
3 2
4 2
3 4
5 1

1 5 3 4 2 3

DFS(u):
While (u存在未被删除的边e(u,v))
删除边e(u,v)
DFS(v)
End
PathSize ← PathSize + 1
Path[ PathSize ] ← u


#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 1005,kMaxM=5005;
int n, m,path_size=0;
int path[kMaxM];//是kMaxM而非kMaxN
int edge[kMaxN][kMaxN];
void dfs(int p)
{
for (int i = 1; i <= n; i++)
{
if (edge[p][i]>0)
{
edge[p][i]--;
edge[i][p]--;
dfs(i);
}
}
path[path_size++] = p;
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
int u, v;
for (int i = 0; i < m; i++)
{
scanf("%d %d", &u, &v);
edge[u][v]++;//防止有重边
edge[v][u]++;
}
dfs(1);
for (int i = 0; i < path_size; i++)
printf("%d ", path[i]);
return 0;
}


AC之后我还尝试了先找出欧拉通路的起点，再从起点开始dfs的方法，这种方法并没有更快，因为不论是从哪个点开始dfs，每个点的for循环都要完整执行，所以时间并不会减少，反而会由于寻找起点而增加时间。

hihoCoder week 49-1-欧拉路·一

hihoCoder week 49-1-欧拉路·一

6 8
1 2
1 4
2 4
2 5
2 3
3 6
4 5
5 6

Full

#include<iostream>
#include<cstdio>
using namespace std;
const int kMax = 10005;
int n, m;
int degree[kMax];
int father[kMax];
int Find(int x)
{
return x == father[x] ? x : (father[x] = Find(father[x]));
}
void Union(int x, int y)
{
father[Find(x)] = Find(y);
}
void Init()
{
for (int i = 1; i <= n; i++)
father[i] = i;
}
bool IsConnected()
{
for (int i = 1; i <= n; i++)
if (father[i] != father[1])
return false;
return true;
}
bool IsEuler()
{
int odd = 0;
for (int i = 1; i <= n; i++)
if (degree[i] & 1)
odd++;
if (odd == 0 || odd == 2)
return true;
return false;
}
int main()
{
scanf("%d %d", &n, &m);
int u, v;
for (int i = 0; i < m; i++)
{
scanf("%d %d", &u, &v);
degree[u]++;
degree[v]++;
Union(u, v);
}
if (IsConnected())
{
if (IsEuler())
printf("Full\n");
else
printf("Part\n");
}
else
printf("Part\n");
return 0;
}


1. 无向图：依次删除图中度数为0或1的点及其关联的边，循环结束，如果还有未删除的点，则存在回路。
2. 有向图：拓扑排序，依次删除图中入度为0的点及其关联的出边，循环结束，如果还有未删除的点，则存在回路。

1. 无向图：使用并查集，最终如果所有节点的父亲都相同，则无向图是连通的。
2. 有向图：判断有向图是否强连通貌似很复杂，Kosaraju算法判断强连通图以及有向图强连通分量的Tarjan算法

POJ 1386-Play on Words

POJ 1386-Play on Words
Play on Words
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 10039 Accepted: 3441
Description
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm'' can be followed by the word motorola''. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".
Sample Input
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
Sample Output
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
Source
Central Europe 1999

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int M=26;
int n,used;
vector<vector<string> > s;
//vector<string> rs;//rs内字符串的先后顺序就是这个游戏的先后顺序
bool dfs(string last)
{
//rs.push_back(last);//记录字符串
used++;
if(used==n)
return true;
else
{
int c=last[last.size()-1]-'a';
int sz=s.size();
for(int i=0;i<sz;i++)
{
if(dfs(s[i]))
return true;
else
used--;//rs.pop_back();//回溯
}
return false;
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t;
string tmp;
cin>>t;
while(t--)
{
cin>>n;
s.clear();
s.resize(M);
for(int i=0;i<n;i++)
{
cin>>tmp;
s[tmp[0]-'a'].push_back(tmp);
}
bool success=false;
for(int i=0;i<M;i++)
{
int sz=s[i].size();
for(int j=0;j<sz;j++)
{
used=0;
success=false;
if(dfs(s[i][j]))
{
success=true;
break;
}
}
if(success)
break;
}
if(success)
cout<<"Ordering is possible."<<endl;
else
cout<<"The door cannot be opened."<<endl;
}
return 0;
}


1.无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)；
2.无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点；
3.有向连通图D是欧拉图，当且仅当D的基图（即其无向图）为连通图且D中每个结点的入度=出度
4.有向连通图D含有欧拉通路，当且仅当D的基图（即其无向图）为连通图且D中除两个结点外，其余每个结点的入度=出度，且此两点满足deg－(u)－deg+(v)=±1。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度）
5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环。
6.如果图G是欧拉图且 H = G - uv，则H有奇数个u,v-迹仅在最后访问v；同时，在这一序列的u,v-迹中，不是路径的迹的条数是偶数。(Todia[1973])

#include<iostream>
#include<string>
using namespace std;
const int M=26;
int n;
int showed[M];//showed[i]表示点i出现过，也就是有边连在i点
int G[M][M];//图
int father[M];//并查集
int degree[M][2];//degree[i][0]入度；degree[i][1]出度
void init_data()
{
for(int i=0;i<M;i++)
{
father[i]=i;
showed[i]=0;
degree[i][0]=0;
degree[i][1]=0;
for(int j=0;j<M;j++)
G[i][j]=0;
}
}
int find_father(int x)
{
return x==father[x]?x:(father[x]=find_father(father[x]));
}
void union_father(int x,int y)
{
father[find_father(x)]=find_father(y);
}
//判断有边的点是否属于一个集合
bool is_one_set()
{
int root=-1;
for(int i=0;i<M;i++)
{
if(showed[i]==1)//有边
{
int tmp=find_father(i);
if(root==-1)
root=tmp;
else if(tmp!=root)
return false;
}
}
return true;
}
bool judge()
{
if(!is_one_set())
return false;
else
{
for(int i=0;i<M;i++)
{
for(int j=0;j<M;j++)
{
if(G[i][j]!=0)
{
degree[i][1]+=G[i][j];
degree[j][0]+=G[i][j];
}
}
}
int a=0,b=0;//a:入度-出度=-1的个数；b:入度-出度=1的个数
for(int i=0;i<M;i++)
{
int rs=degree[i][0]-degree[i][1];
if(rs==-1)
a++;
else if(rs==1)
b++;
else if(rs!=0)
return false;
}
if((a==1&&b==1)||(a==0&&b==0))//欧拉回路或欧拉通路
return true;
return false;
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t,a,b;
string tmp;
cin>>t;
while(t--)
{
cin>>n;
init_data();
for(int i=0;i<n;i++)
{
cin>>tmp;
a=tmp[0]-'a';
b=tmp[tmp.size()-1]-'a';
showed[a]=1;
showed[b]=1;
G[a][b]++;//首字母指向尾字母的边
union_father(a,b);//首字母指向尾字母的边
}
if(judge())
cout<<"Ordering is possible."<<endl;
else
cout<<"The door cannot be opened."<<endl;
}
return 0;
}