【字符串】【最小表示法】Vijos P1683 有根树的同构问题
2024-08-21 22:14:27
题目链接:
题目大意:
给M棵树,每棵N个点,N-1条边,树边有向,问哪些树同构。
题目思路:
【字符串】【最小表示法】
用()表示一个节点,那么三个节点的树 1 2 1 3就可以表示成(()())。
用递归求出每个节点的子树的括号序列,从小到大排序,再在外面加一层(),即为当前结点的括号序列。(这样排完序的括号序列是唯一的)
最终求出每棵树的树根的括号序列,判断是否相等即可。
//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-8)
#define J 10
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#define N 104
using namespace std;
typedef long long LL;
int cas,cass;
int n,m,lll,ans;
double anss;
string s1[N];
struct xxx
{
int next,to;
}a[N];
int last[N];
bool mark[N];
bool cmp(string aa,string bb)
{
if(aa.length()!=bb.length())return aa.length()<bb.length();
int i;
for(i=;i<aa.length();i++)
if(aa[i]!=bb[i])return aa[i]<bb[i];
}
void add(int x,int y)
{
a[++lll].next=last[x];
a[lll].to=y;
last[x]=lll;
}
string dfs(int u)
{
string s[N];
int i,j;
for(i=last[u],j=;i;i=a[i].next,j++)
s[j]=dfs(a[i].to);
sort(s+,s++j,cmp);
string t="(";
for(i=;i<=j;i++)t+=s[i];
t=t+")";
// cout<<u<<" "<<t<<endl;
return t;
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y;
// for(scanf("%d",&cas);cas;cas--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s+1))
while(~scanf("%d",&m))
{
scanf("%d",&n);
for(i=;i<=m;i++)
{
lll=;
mem(last,);mem(mark,);
for(j=;j<n;j++)
{
scanf("%d%d",&x,&y);
add(x,y);mark[y]=;
}
for(j=;j<=n;j++)if(!mark[j])break;
s1[i]=dfs(j);
}
mem(mark,);
for(i=;i<=m;i++)
{
if(mark[i])continue;
printf("%d",i);
mark[i]=;
for(j=i+;j<=m;j++)
if(s1[i]==s1[j])
{
printf("=%d",j);
mark[j]=;
}
puts("");
}
}
return ;
}
/*
// //
*/
最新文章
- svn本地客户端和eclipse插件对应不上解决
- xml Schema import
- [maven] 常用仓库地址
- Linux的IP设置参考
- android 31 GridView
- .Net Mvc Automated Migration 数据迁移
- Ubuntu系统常见问题
- Python打开新世界的大门-入门篇1
- PHP基础入门(二)---入门基础知识必备
- Docker系列08:容器监控
- hive桶表好处
- [From WIKI] IBM Z
- 在IIS上SSL的部署和启动SSL安全【转】
- Win7/Win8/IIS7/IIS8配置ASP/ACCESS
- Appium Python 五:元素定位
- jQuery Ajax实例 ($.ajax_$.post_$.get)
- 简单介绍Java的静态分派和动态分派
- Struts2学习-struts+spring
- codevs 1962 马棚问题--序列型DP
- Navicat for Mysql中错误提示索引过长1071-max key length is 767 byte
热门文章
- 国人编写的开源 .net Ioc 框架——My.Ioc 简介
- vs中debug和release版本的区别(转)
- FluentNHibernate当数据库设置默认值时,使用插入操作,导致默认值没有写入问题
- iOS 延迟执行代码
- iOS英文 汉化,如调用相册,相机改“cancel”,“photos”为“取消”,“相机”
- cos-26上传
- JQUERY 键盘事件
- magento站点还原到本地
- linux安装时提示发生不正常错误问题
- 《学习Opencv》第五章 习题6