6-16 单词 uva10129

了解了欧拉回路和欧拉道路的性质 :

欧拉道路  最多只有两个奇点(不可能只有一个奇点)     并且当有两个奇点的时候  一个奇点入比出多一   一个奇点出比入多一

采用并查集查看是否连同   如果连通块大于等于2  显然不成立

然后判断 入数组 和出数组的个数  当处于个数不相同的时候说明有奇点   判断此时一个为入奇点 一个为出奇点!!

十分巧妙

根据查找连通性不同  有两种方式:

并查集

#include<bits/stdc++.h>
using namespace std;
int f[];
int vis[];
int in[];
int out[]; int find1(int x)
{
return f[x]==x?x:f[x]=find1( f[x] );
} void uni(int a,int b)
{
if(find1(a)!=find1(b))
{
f[a]=b;
}
} char m1[][];
char m2[][]; int main()
{ int cas;cin>>cas;
while(cas--)
{
int n;cin>>n;
memset(vis,,sizeof(vis));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
for(int i=;i<;i++) f[i]=i;
string s;getchar();
while(n--)
{
getline(cin,s);
in[s[]-'a' ]++; out[s[s.size()-]-'a' ]++;
vis[ s[]-'a' ]=vis[ s[s.size()-]-'a' ]=; uni( f[s[]-'a'],f[s[s.size()-]-'a' ]);
} int cnt=;
for(int i=;i<;i++)
{
if(vis[i]&&f[i]==i)cnt++;
}
if(cnt>=){printf("The door cannot be opened.\n");continue;} int ru=-,chu=-; int ok=;
for(int i=;i<;i++)
{ if(vis[i]&&in[i]!=out[i])
{
if(in[i]==out[i]+&&ru==-)ru=;
else if(in[i]==out[i]-&&chu==-)chu=;
else ok=;
} } if(ok)printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n"); } return ;
}

DFS

#include<cstring>
#include<iostream>
#include<cstdio>
#include<cmath>
#define MAXN 100
using namespace std;
int vis[MAXN],G[MAXN][MAXN],N, T,f[MAXN],rank[MAXN], in[MAXN],out[MAXN]; void dfs(int u){
vis[u] = true;
for(int i=; i<MAXN; ++i){
if(G[u][i] && !vis[i])
dfs(i);
}
} int main(){ freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--){
memset(G, , sizeof(G));
memset(in, , sizeof(in));
memset(out, , sizeof(out)); char str[]; scanf("%d",&N); for(int i=; i<N; ++i){
scanf("%s", str);
++G[str[]-'a'][str[strlen(str)-]-'a'];
++out[str[]-'a'];
++in[str[strlen(str)-]-'a'];
} bool flag=true; int num1=, num2=;
for(int i=; i<MAXN; ++i){
if(!flag) break;
if(in[i]!=out[i]){
if(in[i]==out[i]+) { ++num1; }
else if(out[i]==in[i]+) { ++num2; }
else {flag=false; break; }
}
} if(num1 && num2 && num1+num2>) flag=false; if(flag){
memset(vis, , sizeof(vis));
for(int i=; i<MAXN; ++i)
if(out[i]) { dfs(i); break; } bool flag2=true;
for(int i=; i<MAXN; ++i){
if(in[i] && !vis[i]) { flag2=false; break; }
if(out[i] && !vis[i]) { flag2=false; break; }
}
if(flag2) printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
else{
printf("The door cannot be opened.\n");
}
}
return ;
}
上一篇:.Net下实现可扩展的编程方法简述


下一篇:老古董---ASP.NET中aspx页面runat="server"