Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 哈哈没看discuss，同写了个哈希，47ms1A

Posted by KatrineYang at 2016-09-21 12:17:09 on Problem 1343
```#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

const int HASH = 2333;

int k,n;
struct tree{
int size;
int sucNo;
vector<tree*> sucs;
int depth;
int hashVal;
void getSucNo(){
sucNo = sucs.size();
for(int i = 0; i < sucNo; i++){
sucs[i]->getSucNo();
}
}
void getSize(){
size = 0;
for(int i = 0; i < sucNo; i++){
sucs[i]->getSize();
size += sucs[i]->size;
}
size += 1;
}
void getDepth(){
if(!sucNo) {
depth = 0;
return;
}
depth = 0;
for(int i = 0; i < sucNo; i++){
sucs[i]->getDepth();
if(depth < sucs[i]->depth) depth = sucs[i]->depth;
}
depth++;
}
void getHashVal(){
hashVal = 0;
for(int i = 0; i < sucNo; i++){
sucs[i]->getHashVal();
hashVal += sucs[i]->hashVal;
}
hashVal += size*size + depth*depth + sucNo*sucNo;
hashVal %= HASH;
}
}trees[200];

int idx[200];
int wz[200];
vector<int> hashtable[HASH];

for(int i = 0; i < adjNo[rootIdx]; i++){
tree *temp = new tree;
tr->sucs.push_back(temp);
}
}

bool isIsomph(tree *t1, tree *t2){
if(t1->hashVal != t2->hashVal || t1->size != t2->size || t1->depth != t2->depth || t1->sucNo != t2->sucNo){
return 0;
}
bool visited[150] = {0};
for(int i = 0; i < t1->sucNo; i++){
int offset = 0;
for(; offset < t1->sucNo; offset++){
if(!visited[offset] && isIsomph(t1->sucs[i], t2->sucs[offset])) {
visited[offset] = 1;
break;
}
}
if(offset == t1->sucNo) return 0;
}
return 1;
}

int main() {
scanf("%d%d", &k, &n);
if(n == 1){
for(int i = 1; i <= k; i++){
printf("%d ", i);
if(i != k) printf("= ");
}
printf(";\n");
return 0;
}
for(int i = 1; i <= k; i++){
bool bei[110] = {0};
for(int j = 0; j < n-1; j++){
int a, b;
scanf("%d%d", &a, &b);
bei[b] = 1;
}
int root = 1;
for(; root <= n && bei[root]; root++);
//cout << root << endl;
trees[i].getSucNo();
trees[i].getSize();
trees[i].getDepth();
trees[i].getHashVal();
idx[i] = trees[i].hashVal;
wz[i] = hashtable[idx[i]].size();
hashtable[idx[i]].push_back(i);
}
bool visited[200] = {0};
for(int i = 1; i <= k; i++){
if(visited[i]) continue;
printf("%d ", i);
visited[i] = 1;
int sz = hashtable[idx[i]].size();
for(int j = wz[i]+1; j < sz; j++){
int d = hashtable[idx[i]][j];
if(visited[d]) continue;
if(isIsomph(&trees[i], &trees[d])){
visited[d] = 1;
printf("= %d ", d);
}
}
printf(";\n");
}
return 0;
}
```

Followed by: