POJ1129-Channel Allocation

放送局が非常に大きな地域にあるとき、放送局は中継器で信号を中継し、各受信機が強い信号を受信できるようにします.しかしながら、各中継器は、隣接する中継器が互いに干渉しないように慎重に使用されなければならない.隣接する中継器が異なるチャンネルを使用する場合、互いに干渉しない.無線チャネルは限られているため、所与のネットワークに必要な中継チャネルの数は最小限に抑えるべきである.プログラムを作成し、中継ネットワークを読み出し、必要な最低の異なるチャンネル数を求める.
モデリング:N個のノードの無方向図があり、各ノードを染色することを要求し、隣接する2つのノードの色が異なるようにし、最低何色が必要ですか?では、テーマは古典的な図の染色問題になりました.
データが小さいため、最も多い点は26であるため、列挙法を用いて各ノードの染色を処理することができる.あるノードに遍歴すると、そのノードに隣接する各ノードの色はそれと異なるべきであるから、そのノードの周囲のすべてのノードの染色状況を列挙し、使用されていない最小の番号の色を見つけてそのノードを染色すればよい

#include
#include
#include
#include
using namespace std;
const int maxn=233333;
string in;
struct doubi{
    int f,t;
}edge[maxn];
int first[maxn],nextt[maxn],tot;
int ans;
void build(int f,int t)
{
    edge[++tot].f=f;
    edge[tot].t=t;
    nextt[tot]=first[f];
    first[f]=tot;
}
queue<int> q;
int clo[maxn];
bool use[maxn];
void bfs(int u)
{
    clo[u]=1;
    q.push(u);
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(int i=first[p];i;i=nextt[i]){
            int v=edge[i].t;
            if(clo[v]!=clo[p]&&clo[v]>=1) continue;
            int have=0;
            for(int j=first[v];j;j=nextt[j]){
                int t=edge[j].t;
                have|=(1<1));
            }
            int cnt=1;
            while((have&1)!=0){
                have>>=1;
                cnt++;
            }
            clo[v]=cnt;
            q.push(v);
        }
    }
}
void init()
{
    memset(clo,0,sizeof(clo));
    memset(edge,0,sizeof(edge));
    memset(first,0,sizeof(first));
    memset(nextt,0,sizeof(nextt));
    tot=0;
    ans=0;
}
int main()
{
    int n;
    while(cin>>n&&n!=0){
        init();
        for(int i=1;i<=n;i++){
            cin>>in;
            int y=in.length()-1;
            for(int j=2;j<=y;j++){
                build(i,in[j]-'A'+1);
            }
        }
        for(int i=1;i<=n;i++){
            if(!clo[i]) bfs(i);
        }
        for(int i=1;i<=n;i++){
            //cout<
            ans=max(clo[i],ans);
        }
        if(ans==1){
            printf("1 channel needed.
");
        }
        else
        {
            printf("%d channels needed.
",ans);
        }
    }
    return 0;
}