| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 7375 | 2014-08-04T15:34:40 Z | gs13068 | 지도 색칠하기 (GA3_map) | C++ | 0 ms | 0 KB |
int graph[20][20];
int size[20];
int d[20];
bool vis[20];
int q[20];
int qn;
long long NumberOfMaps(int n,int m,int s[],int e[])
{
long long ans=0,cnt;
int i,j,k,l,n,m;
for(i=0;i<m;i++)
{
graph[s[i]-1][size[s[i]-1]++]=e[i]-1;
graph[e[i]-1][size[e[i]-1]++]=s[i]-1;
}
for(i=0;i<(1<<n-1);i++)
{
for(j=0;j<n;j++)vis[j]=false;
cnt=1;
for(l=0;l<n;l++)
{
if(((1<<l)&i)&&!vis[l])
{
qn=0;
d[l]=0;
q[qn++]=l;
vis[l]=true;
for(j=0;j<qn;j++)
{
for(k=0;k<size[q[j]];k++)
{
if((1<<graph[q[j]][k])&i)
{
if(!vis[graph[q[j]][k]])
{
d[graph[q[j]][k]]=1^d[q[j]];
q[qn++]=graph[q[j]][k];
vis[graph[q[j]][k]]=true;
}
else if(d[graph[q[j]][k]]==d[q[j]])
break;
}
}
if(k<size[q[j]])break;
}
if(j<qn)break;
cnt<<=1;
}
}
if(l<n)continue;
for(l=0;l<n;l++)
{
if((!((1<<l)&i))&&!vis[l])
{
qn=0;
d[l]=0;
q[qn++]=l;
vis[l]=true;
for(j=0;j<qn;j++)
{
for(k=0;k<size[q[j]];k++)
{
if(!((1<<graph[q[j]][k])&i))
{
if(!vis[graph[q[j]][k]])
{
d[graph[q[j]][k]]=1^d[q[j]];
q[qn++]=graph[q[j]][k];
vis[graph[q[j]][k]]=true;
}
else if(d[graph[q[j]][k]]==d[q[j]])
break;
}
}
if(k<size[q[j]])break;
}
if(j<qn)break;
cnt<<=1;
}
}
if(l<n)continue;
ans+=cnt;
}
return ans*2;
}