TNFSHOJ 328 I'm Diene!

　　這題其實在考數學，跟甚麼化學根本沒關係，大家應該很很容易看出來。

其實用簡單的說法就是，把重邊去掉之後，把每個連通塊分別壓平，然後看各看有幾個面。

最後輸出面數量*10。

但是甚麼甚麼是面

題目中給了很大的提示，就是正六面體只有五個面。

因為壓平就會變五個。

所以簡單來說，對於所有輸入，要直接將它壓平，以計算有幾個面，

那麼對於一個平面上的圖，可由歐拉公式得知對於每個連通塊

F-E+V=1

F是面數

E是邊數$$
{\displaystyle F-E+V-C=1}

V是頂點數

所以要求的面數就是F=E-V+1

所以就用用並查集 去掉重邊之後算算就行，以下附程式碼。

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) (x).size()

const int MAX=123456;

set<int> st[MAX];

int f[MAX],ans[MAX];

int que(int x){

    if(f[x]==x)    return x;

    return f[x]=que(f[x]);

}

void uni(int x,int y){

    f[que(x)]=que(y);

}

int main(){

    int n,m;

    cin>>n>>m;

    for(int i=0;i<n;i++)    f[i]=i;

    while(m--){

        int x,y;

        cin>>x>>y;

        if(x==y)    continue;

        if(x>y)    swap(x,y);

        st[x].insert(y);

        uni(x,y);

    }   

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

        if(i==que(i))    ans[i]++;

        ans[que(i)]+=SZ(st[i])-1;

    }

    int ma=0;

    for(int i=0;i<n;i++)

        ma=max(ma,ans[i]);

    cout<<ma*10<< '\n';

    return 0;

}