杭電ACM1116――Play on Words~~歐拉路徑與歐拉回路
來源：程序員人生 發布時間：2015-05-22 08:40:38 閱讀次數：3676次
這1題，相比之前做的題目，增加了歐拉路徑的求解。而且這1題是有向圖。題目大概的意思就是成語接龍，能接起來就算可以打開門，因此要斟酌兩種，1種是回路，另外1種是1條路徑。
第1次WR就是由于沒有斟酌回路這1個因素。
有向圖中，歐拉回路與歐拉路徑的求解方法：
1.歐拉回路：
首先固然是圖連通，其次就是所以頂點的入度都等于出度。
2.歐拉路徑：
重要的還是圖連通，然后就是存在1個頂點的出度大入度1，存在1個頂點的入度大出度1，其他頂點的入度等于出度。
這些就不再證明。圖的連通可以用DFS來判斷或并查集，個人喜歡并查集。
下面是AC的代碼，有詳細的注釋：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int par[30], indegree[30], outdegree[30]; //par為并查集，indegree為入度，outdegree為出度
bool vis[30]; //vis為該頂點出現過的標記
int finds(int x) //并查集的查找函數
{
int r = x;
while(r != par[r])
r = par[r];
int i = x, j;
while(i != r) //路徑緊縮
{
j = par[i];
par[i] = r;
i = j;
}
return r;
}
void join(int x, int y) //并查集的合并函數
{
int fx = finds(x);
int fy = finds(y);
if(fx != fy)
par[fy] = fx;
}
int main()
{
int t, n, i;
char str[1005];
scanf("%d", &t);
while(t--)
{
memset(indegree, 0, sizeof(indegree)); //初始化各個數組
memset(outdegree, 0, sizeof(outdegree));
memset(vis, false, sizeof(vis));
for(i = 0; i < 30; i++) //初始化并查集
par[i] = i;
scanf("%d", &n);
while(n--)
{
scanf("%s", str);
int len = strlen(str);
join(str[0] - 'a', str[len - 1] - 'a'); //合并出現的頂點
indegree[str[len - 1] - 'a']++; //相應的入度+1
outdegree[str[0] - 'a']++; //相應的出度+1
vis[str[0] - 'a'] = true; //標記該頂點出現過
vis[str[len - 1] - 'a'] = true;
}
int flag = 0, tag = 0, a = 0, b = 0; //flag來判圖是不是連通，tag為圖中頂點入度不等于出度的個數
<span style="white-space:pre"> </span>//a為入度大出度1的點的個數，b為出度大入度1的點的個數
for(i = 0; i < 30; i++) //判連通
{
if(vis[i] && par[i] == i)
flag++;
}
if(flag > 1) //不連通，直接輸出
{
printf("The door cannot be opened.
");
}
else
{
for(i = 0; i < 30; i++) //查找tag，a， b 的個數
{
if(vis[i] && indegree[i] != outdegree[i])
{
tag++;
}
if(vis[i] && indegree[i] - outdegree[i] == 1)
a++;
if(vis[i] && outdegree[i] - indegree[i] == 1)
b++;
}
if(tag == 0) //tag = 0，存在歐拉回路
printf("Ordering is possible.
");
else if(a == b && a == 1 && tag == 2) //a = 1 && b = 1 && tag = 2.存在歐拉路徑
printf("Ordering is possible.
");
else
printf("The door cannot be opened.
");
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
