希望更丰富的展现?使用Markdown
by caidd @ 2018-08-04 20:16:13
···
#include<bits/stdc++.h>
using namespace std;
int u[100],v[100],a[100],first[100],next[100];
void dfs(int ,int);//点、被染色的可能性;
int color[100],point=0;//piont:用于记录
int V,E,m,ads=0;//ads:计数器
bool colorjudge[100][100];//点、被染色的可能性
int main()
{
int i,j,n,q;
cin>>V>>E>>m;//V顶点 E:边
for(i=1;i<=m;i++)
{
color[i]=i;
}
for(i=1;i<=V;i++)
for(j=1;j<=m;j++)//colorjudge为判断一个点可以染哪个色
colorjudge[i][j]=true;
for(i=1;i<=E;i++)
{
first[i]=next[i]=-1;
}
for(i=1;i<=E;i++)
{
cin>>u[i]>>v[i];//输入起点、终点、边的权;
next[i]=first[u[i]];
first[u[i]]=i;
}
for(i=1;i<=m;i++)
{
colorjudge[1][i]=false;
dfs(1,i);
q=first[1];
while(q!=-1){
colorjudge[v[q]][i]=true;//用于把1的第i种染色情况所造成的影响消除
//cout<<u[k]<<v[k]<<endl;
q=next[q]; }
}
cout<<ads;
}
void dfs(int x,int y)
{
int k,r,w,num=1,k1,c;
k=first[x];
while(k!=-1){
colorjudge[v[k]][y]=false;//有问题,一直循环第一个数据
//cout<<u[k]<<v[k]<<endl;
k=next[k]; }
for(r=1;r<=m&&x<=V;r++)
{
if(colorjudge[x+1][r]==true)
{
colorjudge[x+1][r]=false;
dfs(x+1,r);
k1=first[x+1];//重置,让x+1的一个染色方法排除,从而让其对其他顶点无影响
while(k1!=-1)
{colorjudge[v[k1]][r]=true; k1=next[k1];}
colorjudge[x+1][r]=true;
if(x+1<V) point=0;
if(x+1==V&&point==1) break;
}
if(x==V){//如果图可着色,加
for(w=1;w<=m;w++)
{
if(colorjudge[x][w]==true) {num++;
}
}
point=1;
ads+=num;
break;
}
}
}
···
by 86158615777a @ 2018-08-04 21:15:19
不好意思,我不会用markdown
by 86158615777a @ 2018-08-04 21:15:48
```
#include<bits/stdc++.h>
using namespace std;
int u[100],v[100],a[100],first[100],next[100];
void dfs(int ,int);//点、被染色的可能性;
int color[100],point=0;//piont:用于记录
int V,E,m,ads=0;//ads:计数器
bool colorjudge[100][100];//点、被染色的可能性
int main()
{
int i,j,n,q;
cin>>V>>E>>m;//V顶点 E:边
for(i=1;i<=m;i++)
{
color[i]=i;
}
for(i=1;i<=V;i++)
for(j=1;j<=m;j++)//colorjudge为判断一个点可以染哪个色
colorjudge[i][j]=true;
for(i=1;i<=E;i++)
{
first[i]=next[i]=-1;
}
for(i=1;i<=E;i++)
{
cin>>u[i]>>v[i];//输入起点、终点、边的权;
next[i]=first[u[i]];
first[u[i]]=i;
}
for(i=1;i<=m;i++)
{
colorjudge[1][i]=false;
dfs(1,i);
q=first[1];
while(q!=-1){
colorjudge[v[q]][i]=true;//用于把1的第i种染色情况所造成的影响消除
//cout<<u[k]<<v[k]<<endl;
q=next[q]; }
}
cout<<ads;
}
void dfs(int x,int y)
{
int k,r,w,num=1,k1,c;
k=first[x];
while(k!=-1){
colorjudge[v[k]][y]=false;//有问题,一直循环第一个数据
//cout<<u[k]<<v[k]<<endl;
k=next[k]; }
for(r=1;r<=m&&x<=V;r++)
{
if(colorjudge[x+1][r]==true)
{
colorjudge[x+1][r]=false;
dfs(x+1,r);
k1=first[x+1];//重置,让x+1的一个染色方法排除,从而让其对其他顶点无影响
while(k1!=-1)
{colorjudge[v[k1]][r]=true; k1=next[k1];}
colorjudge[x+1][r]=true;
if(x+1<V) point=0;
if(x+1==V&&point==1) break;
}
if(x==V){//如果图可着色,加
for(w=1;w<=m;w++)
{
if(colorjudge[x][w]==true) {num++;
}
}
point=1;
ads+=num;
break;
}
}
}
```
by 86158615777a @ 2018-08-04 21:16:40
```
#include<bits/stdc++.h>
using namespace std;
int n,k,m;
int u,v,a[100];
int edge[101][101];
long long s=0;
bool b=0;
int color[105];
bool check(int sum){
for(int i=1;i<=sum;i++){
if(edge[i][sum]==true&&color[i]==color[sum]){
return false;
}
}
return true;
}
void dfs(int x)
{
if(x==n+1)
{
s++;
return ;
}
for(int i=1;i<=m;i++){
color[x]=i;//把颜色存下来
if(check(x)==true){
dfs(x+1);
}else{
color[x]=0;//如果冲突则重新打回0
}
}
}
int main()
{
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
cin>>n>>k>>m;
for(int i=1;i<=k;i++)
{
cin>>u>>v;
edge[u][v]=edge[v][u]=1;//a和b有一条边
}
dfs(1);
cout<<s;
return 0;
}
```
by 云朵有点甜_ @ 2020-01-18 08:14:53