Andrew and Chemistry(树的同构)

将一棵树转化为最小表示法，将此时的树哈希一下，同时用map进行标记，就可以判断树是否存在同构

#include <map>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <iostream>

#define scan(x) scanf("%d",&x)

#define scan2(x,y) scanf("%d%d",&x,&y)

using namespace std;

const int Max=1e5+10;

vector<int> a[Max];

map<int,map<int,int> >vis;

map<vector<int>,int>mat;

bool book[Max*100];

int cnt=0;

int dfs(int u,int fa){

     if(vis[u][fa]) return vis[u][fa];

     vector<int> tmp;

     for(int i=0;i<a[u].size();i++)

        if(a[u][i]!=fa)

            tmp.push_back(dfs(a[u][i],u));

     sort(tmp.begin(),tmp.end());

     if(!mat[tmp]) mat[tmp]=++cnt;

     return vis[u][fa]=mat[tmp];

}

int main()

{

    int n,u,v,ans=0;

    scan(n);

    for(int i=1;i<n;i++){

        scan2(u,v);

        a[u].push_back(v);

        a[v].push_back(u);

    }

    for(int i=1;i<=n;i++){

        if(a[i].size()==4) continue;

        v=dfs(i,0);

        if(!book[v]) ans++;

        book[v]=true;

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

Andrew and Chemistry(树的同构)

Andrew and Chemistry(树的同构)

最新文章

热门文章