Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;

string map[11][2];
vector <int> a[10010],path;
int dist[10010];

int furthestPoint(int x,int par)
{
    int ans=x;
    dist[x]=0;
    for (int i=0;i<int(a[x].size());i++)
    {
        int y=a[x][i],t;
        if (y==par) continue;
        t=furthestPoint(y,x);
        if (dist[y]+1>dist[x]) dist[x]=dist[y]+1, ans=t;
    }
    return ans;
}

int findPath(int x,int par,int finish)
{
    path.push_back(x);
    if (x==finish) return 1;
    for (int i=0;i<int(a[x].size());i++)
    {
        int y=a[x][i];
        if (y==par) continue;
        if (findPath(y,x,finish)) return 1;
    }
    path.pop_back();
    return 0;
}

void findGraphCenter(int &c1,int &c2)
{
    int x=furthestPoint(1,0), y=furthestPoint(x,0);
    path.clear();
    findPath(x,0,y);
    c1=path[dist[x]/2]; c2=path[(dist[x]+1)/2];
}

string encode(int x,int par)
{
    vector <string> children;
    string ans="x";
    for (int i=0;i<int(a[x].size());i++)
    {
        int y=a[x][i];
        if (y==par) continue;
        children.push_back(encode(y,x));
    }
    sort(children.begin(),children.end());
    for (int i=0;i<int(children.size());i++) 
    {
        if (i) ans+='-';
        ans+=children[i];
    }
    return ans;
}

int identical(int i,int j)
{
    for (int ii=0;ii<2;ii++)
        for (int jj=0;jj<2;jj++)
            if (map[i][ii]==map[j][jj]) return 1;
    return 0;
}

int main()
{
    int numMap,n,x,y,c1,c2;
    cin >> numMap >> n;
    for (int i=1;i<=numMap;i++)
    {
        for (int j=1;j<=n;j++) a[j].clear();
        for (int j=1;j<n;j++)   scanf("%d%d",&x,&y), a[x].push_back(y), a[y].push_back(x);
        findGraphCenter(c1,c2);
        map[i][0]=encode(c1,0);
        map[i][1]=encode(c2,0);
    }
    for (int i=1;i<=numMap;i++)
    {
        for (int j=1;j<=numMap;j++)
            if (identical(i,j)) cout << j << " ";
        puts("");
    }
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long qword;

const int N = 10004;
const int T = 12;
const qword MUL = 43;

int d[N], par[N], Size[N];
qword power[N];
pair<qword, qword> hashCode[N];
int cntCenter[T];
int nTree, n;

vector<int> a[N];

void dfs(int u) {
    for (int v: a[u]) if (v != par[u]) {
        d[v] = d[u] + 1;
        par[v] = u;
        dfs(v);
    }
}

void initTree(int root) {
    for (int i = 1; i <= n; ++i)
        d[i] = -1, par[i] = 0;
    d[root] = 0;
    dfs(root);
}

int getFarthest() {
    int ans = 1;
    for (int i = 2; i <= n; ++i)
        if (d[i] > d[ans]) ans = i;
    return ans;
}

vector<int> findCenters() {
    vector<int> ans;
    initTree(1);
    int u = getFarthest();
    initTree(u);
    int v = getFarthest();
    int dist = d[v];
    for (int i = 1; i + i <= dist; ++i)
        v = par[v];
    ans.push_back(v);
    if (dist & 1)
        ans.push_back(par[v]);
    return ans;
}

qword getHashCode(int u, int par) {
    Size[u] = 1;
    vector<pair<qword, int> > H;
    for (int v: a[u]) if (v != par) {
        qword cur = getHashCode(v, u);
        Size[u] += Size[v];
        H.push_back({cur, Size[v]});
    }
    sort(H.begin(), H.end());
    qword ans = 1;
    for (auto it: H)
        ans = ans * power[it.second] + it.first;
    ans *= MUL;
    return ans;
}

bool isomorphic(int u, int v) {
    if (cntCenter[u] != cntCenter[v]) return 0;
    if (cntCenter[u] == 1) return hashCode[u].first == hashCode[v].first;
    return hashCode[u].first == hashCode[v].first || hashCode[u].first == hashCode[v].second;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("OLDMAPS.txt", "r", stdin);
#endif // ONLINE_JUDGE
    cin >> nTree >> n;
    power[0] = 1;
    for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * MUL;
    for (int i = 1; i <= nTree; ++i) {
        for (int u = 1; u <= n; ++u) a[u].clear();
        int u, v;
        for (int it = 1; it < n; ++it) {
            cin >> u >> v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        vector<int> C = findCenters();
        cntCenter[i] = C.size();
        hashCode[i].first = getHashCode(C[0], 0);
        if (C.size() > 1)
            hashCode[i].second = getHashCode(C[1], 0);
    }
    vector<int> ans[T];
    for (int i = 1; i <= nTree; ++i) for (int j = 1; j <= nTree; ++j)
        if (isomorphic(i, j)) ans[i].push_back(j);
    for (int i = 1; i <= nTree; ++i) {
        for (int it: ans[i]) cout << it << ' ';
        cout << endl;
    }
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <vector>

#define MAXN 10111
#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define V vector<int>
#define PB push_back

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//Buffer reading


using namespace std;

int debug=0;
int n,t;
V ke[11][MAXN];
int d[MAXN],save[MAXN],father[MAXN];
int root[11][2];
int mahoa[11][2][MAXN],weight[MAXN],startof[MAXN],tmp[MAXN],ind[MAXN];

void input() {
    GN(t); GN(n);
    int u,v;
    FOR(tr,1,t) {
        FOR(i,1,n-1) {
            GN(u); GN(v);
            ke[tr][u].PB(v);
            ke[tr][v].PB(u);
        }
    }
}

void dfs(int tr,int u) {
    save[u]=u; d[u]=0;
    FORV(v,ke[tr][u]) {
        if (father[*v]) continue;
        father[*v]=u;
        dfs(tr,*v);
        if (d[*v]+1>d[u]) {
            d[u]=d[*v]+1;
            save[u]=save[*v];
        }
    }
}

void init() {
    FOR(tr,1,t) {
        memset(father,0,sizeof father);
        father[1]=1; dfs(tr,1);
        int u=save[1];

        memset(father,0,sizeof father);
        father[u]=u; dfs(tr,u);

        int l=d[u]; u=save[u];
        FOR(i,1,l/2) u=father[u];
        root[tr][0]=u;
        if (l&1) root[tr][1]=father[u];
        else root[tr][1]=u;
    }
    if (debug) {
        cout<<"Roots of trees:\n";
        FOR(i,1,t) cout<<root[i][0]<<" "<<root[i][1]<<endl;
    }
}

int *p;
inline bool lower(int u, int v) {
    int su=startof[u], sv=startof[v];
    if (p[su]!=p[sv]) return p[su]<p[sv];
    FOR(i,1,p[su])
        if (p[su+i]!=p[sv+i]) return p[su+i]<p[sv+i];

    return false;
}

inline void encode(int tr,int root,int mahoa[]) {
    weight[root]=1;

    FORV(v,ke[tr][root]) {
        if (father[*v]) continue;

        startof[*v]=weight[root];
        father[*v]=root;
        encode(tr,*v,mahoa+startof[*v]);

        weight[root]+=weight[*v]+1;
    }
    weight[root]--;

    p=mahoa;
    p[0]=weight[root];
    int sc=0; FORV(v,ke[tr][root]) if (father[*v]==root) ind[++sc]=*v;
    if (sc>1) sort(ind+1,ind+sc+1,lower);

    if (sc>1) {
        int now=1;
        FOR(i,0,mahoa[0]) tmp[i]=mahoa[i];
        FOR(i,1,sc) {
            int u=ind[i];
            FOR(i,0,weight[u])
                *(p+now+i)=tmp[startof[u]+i];
            now+=weight[u]+1;
        }
    }

    if (debug) {
        cout<<endl;
        cout<<root<<endl;
        FOR(i,0,weight[root]) cout<<mahoa[i]<<" "; cout<<endl;
    }
}

inline bool isEqual(int a[],int b[]) {
    FOR(i,0,n-1)
        if (a[i]!=b[i]) return false;
    return true;
}

inline bool check(int tr1,int tr2) {
    FOR(m1,0,1)
    FOR(m2,0,1)
        if (isEqual(mahoa[tr1][m1],mahoa[tr2][m2])) return true;

    return false;
}

void solve() {
    FOR(tr,1,t) {
        memset(father,0,sizeof father);
        father[root[tr][0]]=-1; encode(tr,root[tr][0],mahoa[tr][0]);

        memset(father,0,sizeof father);
        father[root[tr][1]]=-1; encode(tr,root[tr][1],mahoa[tr][1]);
    }

    if (debug)
        FOR(tr,1,t) {
            cout<<endl;
            cout<<"Code of trees:\n";
            FOR(typ,0,1) {
                FOR(i,0,n-1)
                    cout<<mahoa[tr][typ][i]<<" "; 
                cout<<endl;
            }
        }

    if (debug) cout<<"\nResult:\n";
    FOR(tr1,1,t) {
        FOR(tr2,1,t)
            if (check(tr1,tr2)) cout<<tr2<<" ";
        cout<<endl;
    }
}

int main() {
    input();
    init();
    solve();
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}
// Dinic

int t, n, u, v;
vector<int> V[11][10011];
pair<long long, long long> f[11][10011];

long long hash(long long x){
    return x * x * x * x + 11 * x * x + 37 * x + 1397;
}

void duyet(int i, int par, int u){
    f[i][u].fi = V[i][u].size();
    f[i][u].se = 1;
    rep(j, V[i][u].size()){
        v = V[i][u][j];
        f[i][u].se *= hash(V[i][v].size());
        if(v != par){
            duyet(i, u, v);
        }
    }
}

bool bang(int i, int j){
    for(int k = 1; k <= n; k++) if(f[i][k] != f[j][k]) return false;
    return true;
}

int main(){
    //OPEN();
    scanf("%d %d", &t, &n);
    FOR(i, 1, t){
        rep(j, n - 1){
            scanf("%d %d", &u, &v);
            V[i][u].PB(v);
            V[i][v].PB(u);
        }
        duyet(i, 0, 1);
        sort(f[i] + 1, f[i] + n + 1);
    }
    FOR(i, 1, t){
        FOR(j, 1, t) if(bang(i, j)){
            printf("%d ",j);
        }
        printf("\n");
    }    
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int T,n;

struct Node{
    vector<Node*> v;    
};

bool CMP(Node*a,Node*b);

int cmp(Node*a,Node*b) {
    if(a->v.size() < b->v.size()) return -1;
    if(a->v.size() > b->v.size()) return 1;
    sort(a->v.begin(),a->v.end(),CMP);
    sort(b->v.begin(),b->v.end(),CMP);
    for(int i=0;i<a->v.size();++i) {
        int t = cmp(a->v[i],b->v[i]);
        if(t!=0)return t;
    }
    return 0;
}

bool CMP(Node*a,Node*b){
    return cmp(a,b) == -1;  
}

struct Tree {
    vector<int> ke[10010];
    int h[10010], fa[10010];
    Node *n1, *n2;
    int id;

    void dfs1(int i,int fi) {
        for(int k=0;k<ke[i].size();++k) {
            int j = ke[i][k];
            if(j != fi) {
                h[j] = h[i] + 1;
                dfs1(j, i); 
            }
        }   
    }

    void dfs2(int i,int fi) {
        for(int k=0;k<ke[i].size();++k) {
            int j = ke[i][k];
            if(j != fi) {
                h[j] = h[i] + 1;
                fa[j] = i;
                dfs2(j, i); 
            }
        }   
    }

    Node* make_tree(int i,int fi) {
        Node *n = new Node();
        for(int k=0;k<ke[i].size();++k) {
            int j = ke[i][k];
            if(j != fi) {
                n->v.push_back(make_tree(j,i));
            }
        }
        return n;
    }

    void find_mid() {
        dfs1( 1, -1);
        int newroot = max_element(h + 1, h + 1 + n) - h;
        h[newroot] = 0;
        dfs2( newroot, -1);
        int z = max_element(h + 1, h + 1 + n) - h;
        int hei = h[z];
        for(int i=0;i<hei/2;++i) z = fa[z];
        n1 = n2 = NULL;
        n1 = make_tree(z, -1);
        if(hei % 2 == 1){
            z = fa[z];
            n2 = make_tree(z, -1);  
        }
    }
};

Tree a[11];
int f[11];

int getroot(int i){
    if(f[i]<0)return i;else return getroot(f[i]);   
}

int main() {
    scanf("%d%d",&T,&n);
    for(int t=0;t<T;++t){
        for(int i=0;i+1<n;++i) {
            int u,v;
            scanf("%d%d",&u,&v);
            a[t].ke[u].push_back(v);
            a[t].ke[v].push_back(u);
        }   
        a[t].id = t + 1;
        a[t].find_mid();
    }
    memset(f,-1,sizeof(f));
    for(int i=0;i<T;++i) {
        for(int j=i+1;j<T;++j) if(getroot(i)!=getroot(j)) {
            if(cmp(a[i].n1,a[j].n1) == 0){
                f[getroot(i)]+=f[getroot(j)];
                f[getroot(j)]=i;    
            }
            else if(a[j].n2!=NULL && a[i].n2!=NULL && cmp(a[i].n1,a[j].n2) == 0){
                f[getroot(i)]+=f[getroot(j)];
                f[getroot(j)]=i;    
            }
        }
    }
    for(int i=0;i<T;++i) {
        for(int j=0;j<T;++j) if(getroot(j) == getroot(i)) cout << j + 1 << " ";
        cout << endl;   
    }
    return 0;
}